Metraipolis › archive › dc_dd25d0cbe90f

Grafo perfetto — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Grafo_perfetto
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T14:48:39.020Z
SHA-256 of the archived text
02fd1f94a237b3810ef5d4475e0c506eda5784997a64b8749a47d3fe99c692b6
Stable URL of this page
https://metraipolis.com/documento/dc_dd25d0cbe90f

How to cite

Grafo perfetto — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Grafo_perfetto (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_dd25d0cbe90f (Metraipolis archive dc_dd25d0cbe90f, sha256 02fd1f94a237b3810ef5d4475e0c506eda5784997a64b8749a47d3fe99c692b6)
BibTeX
@misc{dcdd25d0cbe90f,
  title = {Grafo perfetto — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Grafo_perfetto},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_dd25d0cbe90f; sha256 02fd1f94a237b3810ef5d4475e0c506eda5784997a64b8749a47d3fe99c692b6},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Grafo_perfetto. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più grande di quel sottografo. Grazie al teorema del grafo perfetto forte, sappiamo dal 2002 che i grafi perfetti sono la stessa cosa dei grafi di Berge. Un grafo G è un grafo di Berge se né G né il suo complemento hanno un ciclo indotto di lunghezza dispari uguale a 5 o superiore. I grafi perfetti comprendono molte importanti famiglie di grafi, e servono a unificare risultati che collegano le colorazioni e le cricche in quelle famiglie. Per esempio, in tutti i grafi perfetti, il problema della colorazione dei grafi, il problema della cricca massima e il problema del massimo insieme indipendente possono essere tutti risolti in tempo polinomiale. In aggiunta, parecchi importanti teoremi di minimo e massimo in combinatoria, come il teorema di Dilworth, possono essere espressi in termini della perfezione di certi grafi associati. La teoria dei grafi perfetti si sviluppò da un risultato del 1958 di Tibor Gallai che in linguaggio moderno può essere interpretato affermando che il complemento di un grafo bipartito è perfetto; questo risultato può anche essere visto come un semplice equivalente del teorema di König, un risultato molto anteriore che collega gli accoppiamenti e le coperture dei vertici nei grafi bipartiti. Il primo uso della locuzione "grafo perfetto" pare che sia in un saggio del 1963 di Claude Berge, dal quale prendono nome i grafi di Berge. In questo saggio egli unificò il risultato di Gallai con vari risultati simili definendo i grafi perfetti, e congetturò l'equivalenza delle definizioni di grafo perfetto e di grafo di Berge; la congettura di Berge fu dimostrata nel 2002 come il teorema del grafo perfetto forte.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»).
Fonte: Wikipedia in italiano, voce «Grafo perfetto» — https://it.wikipedia.org/wiki/Grafo_perfetto
Wikidata Q1187620 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1187620
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Grafo_perfetto?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 152602126, consultata il 2026-10-07T14:21:41.010Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 55db6bc8b701a4ee1f63bfe1616fee835eb0bd01ba89a76bfff8bab9f446bdd8