Albertsonova domněnka - Albertson conjecture
![]() | Nevyřešený problém v matematice: (více nevyřešených úloh z matematiky) |

v kombinační matematika, Albertsonova domněnka je neprokázaný vztah mezi číslo křížení a chromatické číslo a graf. Je pojmenována po Michaelovi O. Albertsonovi, profesorovi na Smith College, který to v roce 2007 uvedl jako domněnku;[1] je to jeden z jeho mnoha dohadů zbarvení grafu teorie.[2] Domněnka uvádí, že mezi všemi požadovanými grafy barvy, kompletní graf je ten s nejmenším počtem křížení. Pokud je možné nakreslit graf s menším počtem křížení, ekvivalentně , pak podle domněnky může být zbarveno méně než barvy.
Dohadovaný vzorec pro minimální počet křížení
Je jednoduché ukázat, že grafy s omezeným číslem křížení mají omezené chromatické číslo: jeden může přiřadit odlišné barvy koncovým bodům všech hran hran a pak zbarvit zbývající čtyři rovinný graf. Albertsonova domněnka nahrazuje tento kvalitativní vztah mezi číslem křížení a barvením přesnějším kvantitativním vztahem. Konkrétně jiná domněnka Richard K. Guy (1972 ) uvádí, že číslo křížení celého grafu je
Je známo, jak kreslit úplné grafy s tolika kříženími, a to umístěním vrcholů do dvou soustředných kruhů; není známo, zda existuje lepší kresba s menším počtem přejezdů. Posílená formulace Albertsonova domněnky je tedy každá -chromatický graf má číslo křížení alespoň tak velké jako pravá strana tohoto vzorce.[3] Tato posílená domněnka by byla pravdivá, jen kdyby byla pravdivá jak Guyova domněnka, tak Albertsonova domněnka.
Asymptotické hranice
Slabší forma domněnky, prokázaná M. Schaeferem,[3] uvádí, že každý graf s chromatickým číslem má číslo křížení (použitím velká omega notace ), nebo ekvivalentně, že každý graf s číslem křížení má chromatické číslo . Albertson, Cranston & Fox (2009) zveřejnil jednoduchý důkaz o těchto mezích spojením skutečnosti, že každý minimální -chromatický graf má alespoň minimální stupeň (protože jinak chamtivé zbarvení by používalo méně barev) společně s nerovnost křížení čísel podle kterého každý graf s má číslo křížení . Stejným zdůvodněním ukazují, že je to protiklad Albertsonova domněnky o chromatickém čísle (pokud existuje) musí mít méně než vrcholy.
Speciální případy
Albertsonova domněnka je prázdně pravda pro . V těchto případech má křížení číslo nula, takže domněnka uvádí pouze to, že -chromatické grafy mají číslo křížení větší nebo rovné nule, což platí pro všechny grafy. Pouzdro Albertsonova domněnky je ekvivalentní s čtyřbarevná věta, že libovolný planární graf může být zbarven čtyřmi nebo méně barvami, protože pouze u grafů vyžadujících méně křížení než jeden křížení jsou rovinné grafy a z domněnky vyplývá, že všechny by měly být maximálně 4-chromatické. Díky úsilí několika skupin autorů je nyní známo, že domněnka platí pro všechny .[4] Pro každé celé číslo , Luiz a Richter představili rodinu -barevné kritické grafy, které neobsahují dělení celého grafu ale mít číslo křížení alespoň to .[5]
Související dohady
K dispozici je také připojení k internetu Hadwigerův dohad, důležitý otevřený problém v kombinatorice týkající se vztahu mezi chromatickým číslem a existencí velkého kliky tak jako nezletilí v grafu.[6] Varianta hadwigerského dohadu, kterou uvedl György Hajós, je to každý -chromatický graf obsahuje a pododdělení z ; pokud by to byla pravda, následovala by Albertsonova domněnka, protože číslo křížení celého grafu je přinejmenším stejně velké jako číslo křížení kteréhokoli z jeho pododdělení. Nyní jsou však známy protiklady k Hajósově domněnce,[7] toto spojení tedy neposkytuje cestu k důkazu Albertsonova domněnky.
Poznámky
- ^ Podle Albertson, Cranston & Fox (2009), domněnku vytvořil Albertson na zvláštním zasedání Americká matematická společnost v Chicagu, které se konalo v říjnu 2007.
- ^ Hutchinson, Joan P. (19. června 2009), Na památku Michaela O. Albertsona, 1946–2009: sbírka jeho vynikajících dohadů a otázek v teorii grafů (PDF)Skupina aktivit SIAM pro diskrétní matematiku.
- ^ A b Albertson, Cranston & Fox (2009).
- ^ Oporowski & Zhao (2009); Albertson, Cranston & Fox (2009); Barát & Tóth (2010); Ackerman (2019).
- ^ Luiz & Richter (2014).
- ^ Barát & Tóth (2010).
- ^ Catlin (1979); Erdős & Fajtlowicz (1981).
Reference
- Ackerman, Eyal (2019), „Na topologických grafech s maximálně čtyřmi přechody na hranu“, Výpočetní geometrie, 85: 101574, 31, arXiv:1509.01932, doi:10.1016 / j.comgeo.2019.101574, PAN 4010251
- Albertson, Michael O .; Cranston, Daniel W .; Fox, Jacobe (2009), „Barvy, přechody a kliky“ (PDF), Electronic Journal of Combinatorics, 16: R45, arXiv:1006.3783, Bibcode:2010arXiv1006.3783A.
- Barát, János; Tóth, Géza (2010), „Směrem k Albertsonově domněnce“, Electronic Journal of Combinatorics, 17 (1): R73, arXiv:0909.0413, Bibcode:2009arXiv0909.0413B.
- Catlin, P. A. (1979), „Hajósova hypotéza zabarvení grafů: variace a protipříklady“, Journal of Combinatorial Theory, Řada B, 26 (2): 268–274, doi:10.1016/0095-8956(79)90062-5.
- Erdős, Paul; Fajtlowicz, Siemion (1981), „O domněnce Hajóse“, Combinatorica, 1 (2): 141–143, doi:10.1007 / BF02579269.
- Guy, Richard K. (1972), "Crossing numbers of graphs", in Alavi, Y.; Lick, D. R .; White, A. T. (eds.), Teorie grafů a aplikace: Sborník z konference na Western Michigan University, Kalamazoo, Mich., 10. – 13. Května 1972, New York: Springer-Verlag, s. 111–124. Jak uvádí Albertson, Cranston & Fox (2009).
- Oporowski, B .; Zhao, D. (2009), „Barvení grafů křížením“, Diskrétní matematika, 309 (9): 2948–2951, arXiv:matematika / 0501427, doi:10.1016 / j.disc.2008.07.040.
- Luiz, Atílio; Richter, Bruce (2014), „Poznámky k domněnce Baráta a Tótha“, Electronic Journal of Combinatorics, 21 (1): P1,57.