Gyárfás – Sumnerova domněnka - Gyárfás–Sumner conjecture
Nevyřešený problém v matematice: Vytváří zákaz jak stromu, tak kliky jako indukovaných podgrafů grafy omezeného chromatického čísla? (více nevyřešených úloh z matematiky) |
v teorie grafů, Gyárfás – Sumnerova domněnka ptá se, zda pro každého strom a kompletní graf , grafy ani s jedním ani tak jako indukované podgrafy může být správně zbarvené používající pouze konstantní počet barev. Rovněž se ptá, zda -bezplatné grafy jsou - omezený.[1]Je pojmenován po András Gyárfás a David Sumner, kteří jej formulovali samostatně v letech 1975 a 1981.[2][3] Zůstává neprokázané.[4]
V této domněnce není možné jej nahradit grafem s cykly. Tak jako Paul Erdős a András Hajnal ukázaly, že existují grafy bez trojúhelníků s libovolně velkým chromatickým číslem a současně libovolně velkým obvod.[5] Pomocí těchto grafů lze získat grafy, které se vyhnou jakémukoli pevnému výběru cyklického grafu a kliky (s více než dvěma vrcholy) jako indukovaných podgrafů a překročí jakoukoli pevnou vazbu na chromatické číslo.[1]
Je známo, že domněnka platí pro určité speciální volby , počítaje v to cesty,[6] hvězdy a stromy o poloměru dva.[7]Je také známo, že pro každý strom , grafy, které neobsahují a pododdělení z jsou - omezený.[1]
Reference
- ^ A b C Scott, A. D. (1997), „Indukované stromy v grafech s velkým chromatickým číslem“, Journal of Graph Theory, 24 (4): 297–311, doi:10.1002 / (SICI) 1097-0118 (199704) 24: 4 <297 :: AID-JGT2> 3.3.CO; 2-X, PAN 1437291
- ^ Gyárfás, A. (1975), "On Ramsey krycí čísla", Nekonečné a konečné množiny (Colloq., Keszthely, 1973; věnováno P. Erdősovi k jeho 60. narozeninám), sv. IIColloq. Matematika. Soc. János Bolyai, 10, Amsterdam: Severní Holandsko, str. 801–816, PAN 0382051
- ^ Sumner, D. P. (1981), „Podstromy grafu a chromatické číslo“, Teorie a aplikace grafů (Kalamazoo, Mich., 1980), Wiley, New York, str. 557–576, PAN 0634555
- ^ Chudnovský, Maria; Seymour, Paule (2014), „Rozšíření dohadů Gyárfás-Sumner“, Journal of Combinatorial Theory, Řada B, 105: 11–16, doi:10.1016 / j.jctb.2013.11.002, PAN 3171779
- ^ Erdős, P.; Hajnal, A. (1966), "Na chromatickém počtu grafů a set-systémů" (PDF), Acta Mathematica Academiae Scientiarum Hungaricae, 17: 61–99, doi:10.1007 / BF02020444, PAN 0193025
- ^ Gyárfás, A. (1987), „Problémy ze světa obklopujícího dokonalé grafy“, Sborník mezinárodní konference o kombinatorické analýze a jejích aplikacích (Pokrzywna, 1985), Zastosowania Matematyki, 19 (3–4): 413–441 (1988), PAN 0951359
- ^ Kierstead, H. A .; Penrice, S. G. (1994), „Radius two trees specify χ-bounded classes“, Journal of Graph Theory, 18 (2): 119–129, doi:10,1002 / jgt.3190180203, PAN 1258244
externí odkazy
- Grafy se zakázaným indukovaným stromem jsou ohraničeny chi, Otevřená problémová zahrada