Χ ohraničené - Χ-bounded
v teorie grafů, a - omezený rodina grafů je ten, pro který existuje nějaká funkce tak, že pro každé celé číslo grafy v bez č -vrchol klika může být barevný maximálně barvy. Tento koncept a jeho notaci formuloval András Gyárfás.[1] Použití řeckého dopisu chi v termínu -bounded je založen na skutečnosti, že chromatické číslo grafu se běžně označuje .
Nenáročnost
Není pravda, že rodina všech grafů je -bounded.As Zykov (1949) a Mycielski (1955) ukázal, že existují grafy bez trojúhelníků libovolně velkého chromatického čísla,[2][3] takže pro tyto grafy není možné definovat konečnou hodnotu .Tím pádem, -boundedness je netriviální koncept, platný pro některé rodiny grafů a nepravdivý pro ostatní.[4]
Specifické třídy
Každá třída grafů ohraničené chromatické číslo je (triviálně) - ohraničený, s rovná se vázané na chromatické číslo. To zahrnuje například rovinné grafy, bipartitní grafy, a grafy ohraničené zvrhlost. Navíc grafy, ve kterých číslo nezávislosti je také omezený -bounded, as Ramseyova věta znamená, že mají velké kliky.
Vizingova věta lze interpretovat jako prohlášení, že spojnicové grafy jsou - ohraničený, s .[5][6] The grafy bez drápů obecněji jsou také - vázaný na . To lze vidět pomocí Ramseyho věty, která ukazuje, že v těchto grafech musí být vrchol s mnoha sousedy součástí velké kliky. Tato vazba je v nejhorším případě téměř těsná, ale spojené grafy bez drápů, které obsahují tři vzájemně - nesousedící vrcholy mají ještě menší chromatické číslo, .[5]
jiný rodiny ohraničených grafů zahrnují:
- The perfektní grafy, s
- Grafy boxicita dva[7]
- Grafy ohraničené šířka kliky[8]
- The průsečíkové grafy zmenšených a přeložených kopií jakéhokoli kompaktního konvexního tvaru v rovině[9]
- The kruhové grafy, a (zobecňující kruhové grafy) „vnější řetězce“, průsečíkové grafy ohraničených křivek v rovině, které se všechny dotýkají neomezené plochy dohoda křivek[10]
Přestože průnikové grafy konvexních tvarů, kruhové grafy a vnější řetězce jsou všechny speciální případy řetězcové grafy, samotné řetězcové grafy nejsou Zahrnují jako speciální případ průsečíkové grafy úsečky, které také nejsou - omezený.[4]
Nevyřešené problémy
Nevyřešený problém v matematice: Jsou všechny třídy grafů bez stromů -vázaný? (více nevyřešených úloh z matematiky) |
Podle Gyárfás – Sumnerova domněnka, pro každého strom , grafy, které neobsahují jako indukovaný podgraf jsou - omezený. Například by to zahrnovalo případ grafů bez drápů, protože dráp je speciální druh stromu. Je však známo, že domněnka je pravdivá pouze pro některé speciální stromy, včetně cesty[1] a poloměr dva stromy.[11]
Další nevyřešený problém dne -bounded byl položen Louis Esperet, který se zeptal, zda každá dědičná třída grafů, která je -bounded má funkci která roste nanejvýš polynomiálně jako funkce .[6]
Nevyřešený problém v matematice: Dědičně -bounded graph class, is the chromatic number at most polynomial in the clique size? (více nevyřešených úloh z matematiky) |
Reference
- ^ A b 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
- ^ Zykov, A. A. (1949), „О некоторых свойствах линейных комплексов“ [O některých vlastnostech lineárních komplexů], Rohož. Sbornik N.S. (v Rusku), 24 (66): 163–188, PAN 0035428. Přeloženo do angličtiny v angličtině Amer. Matematika. Soc. Překlad, 1952, PAN0051516. Jak uvádí Pawlik a kol. (2014)
- ^ Mycielski, Jan (1955), „Sur le coloriage des graphs“, Colloq. Matematika. (francouzsky), 3: 161–162, PAN 0069494
- ^ A b Pawlik, Arkadiusz; Kozik, Jakub; Krawczyk, Tomasz; Lasoń, Michał; Micek, Piotr; Trotter, William T.; Walczak, Bartosz (2014), „Průsečíkové grafy přímkových segmentů s velkým chromatickým číslem bez trojúhelníků“, Journal of Combinatorial Theory, Řada B, 105: 6–10, arXiv:1209.1595, doi:10.1016 / j.jctb.2013.11.001, PAN 3171778
- ^ A b Chudnovský, Maria; Seymour, Paule (2010), "Graphs-Claw-free graphs VI. Coloring", Journal of Combinatorial Theory, Řada B, 100 (6): 560–572, doi:10.1016 / j.jctb.2010.04.005, PAN 2718677
- ^ A b Karthick, T .; Maffray, Frédéric (2016), „Vizing vázán na chromatické číslo u některých tříd grafů“, Grafy a kombinatorika, 32 (4): 1447–1460, doi:10.1007 / s00373-015-1651-1, PAN 3514976
- ^ Asplund, E .; Grünbaum, B. (1960), "O problému barvení", Mathematica Scandinavica, 8: 181–188, doi:10,7146 / math.scand.a-10607, PAN 0144334
- ^ Dvořák, Zdeněk; Král ', Daniel (2012), „Třídy grafů s malými řadovými rozklady jsou -bounded ", Electronic Journal of Combinatorics, 33 (4): 679–683, arXiv:1107.2161, doi:10.1016 / j.ejc.2011.12.005, PAN 3350076
- ^ Kim, Seog-Jin; Kostochka, Alexandr; Nakprasit, Kittikorn (2004), „Na chromatickém počtu křižovatek konvexních množin v rovině“, Electronic Journal of Combinatorics, 11 (1), R52, PAN 2097318
- ^ Rok, Alexandre; Walczak, Bartosz (2014), „Outerstring graphs are -bounded ", Sborník z třicátého výročního symposia o výpočetní geometrii (SoCG'14), New York: ACM, s. 136–143, doi:10.1145/2582112.2582115, PAN 3382292
- ^ Kierstead, H. A .; Penrice, S. G. (1994), „Poloměr dvou stromů specifikuje -ohraničené třídy ", Journal of Graph Theory, 18 (2): 119–129, doi:10,1002 / jgt.3190180203, PAN 1258244
externí odkazy
- Chi-ohraničený, Otevřená problémová zahrada