Silná věta o perfektních grafech

V teorii grafů udává silná věta o perfektních grafech charakterizaci perfektních grafů pomocí zakázaných podgrafů. Podle věty je graf perfektní právě tehdy, když neobsahuje lichou díru (tj. lichou kružnici délky alespoň 5) ani lichou antidíru (tj. doplněk liché díry) jako indukovaný podgraf. Claude Berge představil toto tvrzení jako hypotézu roku 1961. Důkaz hypotézy uveřejnili Maria Chudnovsky, Neil Robertson, Paul Seymour a Robin Thomas roku 2006.[1]

Reference

  1. ↑ CHUDNOVSKY, Maria; ROBERTSON, Neil; SEYMOUR, Paul. The Strong Perfect Graph Theorem. Annals of Mathematics. 2006, roč. 164, čís. 1, s. 51–229. Dostupné online [cit. 2024-04-15]. ISSN 0003-486X. 
Pahýl
Pahýl
 Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.