Jedinečně barevný graf - Uniquely colorable graph

v teorie grafů, a jedinečně barevný graf je k-chromatický graf, který má jen jeden možný (správné) k-zbarvení až do permutace barev. Ekvivalentně existuje pouze jeden způsob rozdělení jeho vrcholů k nezávislé sady a neexistuje způsob, jak je rozdělit k-1 nezávislé sady.

Příklady

A kompletní graf je jedinečně barevný, protože jediné správné zbarvení je takové, které každému vrcholu přiřadí jinou barvu.

Každý k-strom je jednoznačně (k + 1) -barevné. Jedinečně 4barevné rovinné grafy je známo, že jsou přesně Apollonské sítě, tj. rovinné 3-stromy (Fowler 1998 ).

Vlastnosti

Některé vlastnosti jedinečně k-barevný graf G s n vrcholy a m hrany:

  1. m ≥ (k - 1) n - k(k-1)/2. (Truszczyński 1984; Xu 1990 )

Související pojmy

Minimální nedokonalost

A minimální nedokonalý graf je graf, ve kterém je každý podgraf perfektní. Odstranění jakéhokoli vrcholu z minimálního nedokonalého grafu zanechává jedinečně barevný podgraf.

Jedinečná barevnost hran

Unikátní zbarvení 3 hran zobecněný Petersenův graf G(9,2)

A jedinečně barevný graf od okraje je k- hrana-chromatická graf, který má jen jeden možný (správné) k-obarvení okraje až do permutace barev. Jedinými jedinečně barevnými grafy se dvěma okraji jsou cesty a cykly. Pro všechny k, hvězdy K.1,k jsou jediné jedinečně k-obrázkové barvicí grafy. Navíc, Wilson (1976) domnělý a Thomason (1978) dokázal, že když k ≥ 4, jsou také jedinými členy této rodiny. Existují však jednoznačně 3barevné barevné grafy, které do této klasifikace nezapadají, například graf trojúhelníková pyramida.

Pokud kubický graf je jedinečně barevný na 3 hranách, musí mít přesně tři Hamiltonovské cykly, tvořené hranami se dvěma ze svých tří barev, ale některé kubické grafy s pouhými třemi hamiltonovskými cykly nejsou jednoznačně barvitelné na 3 hranách (Thomason 1982 ). Velmi jednoduché rovinný krychlový graf, který je jedinečně barevný na 3 hranách, obsahuje trojúhelník (Fowler 1998 ), ale W. T. Tutte  (1976 ) poznamenal, že zobecněný Petersenův graf G(9,2) je nerovinný, bez trojúhelníků a jedinečně barevný na 3 hranách. Po mnoho let to byl jediný známý takový graf a předpokládalo se, že je to jediný takový graf (viz Bollobás 1978 a Schwenk 1989 ), ale nyní je známo nekonečně mnoho neplanárních kubických jedinečných tříbarevných barevných grafů bez trojúhelníků (belcastro & Haas 2015 ).

Jedinečná celková barevnost

A jedinečně barevný graf je k-celkově-chromatický graf to má jen jedno možné (správné) k-celkové zbarvení až do permutace barev.

Prázdné grafy, cesty, a cykly délky dělitelné 3 jsou jedinečně celkové barevné grafy.Mahmoodian & Shokrollahi (1995) domnívali se, že jsou také jedinými členy této rodiny.

Některé vlastnosti jedinečně k-celkově barevný graf G s n vrcholy:

  1. χ ″ (G) = Δ (G) + 1, pokud G = K.2. (Akbari a kol. 1997 )
  2. Δ (G) ≤ 2 δ (G). (Akbari a kol. 1997 )
  3. Δ (G) ≤ n / 2 + 1. (Akbari 2003 )

Zde χ ″ (G) je celkové chromatické číslo; Δ (G) je maximální stupeň; a δ (G) je minimální stupeň.

Reference

  • Akbari, S. (2003), „Dva dohady o jedinečně zcela barevných grafech“, Diskrétní matematika, 266 (1–3): 41–45, doi:10.1016 / S0012-365X (02) 00797-5, PAN  1991705.
  • Akbari, S .; Behzad, M .; Hajiabolhassan, H .; Mahmoodian, E. S. (1997), „Uniquely total colorable graphs“, Grafy a kombinatorika, 13 (4): 305–314, doi:10.1016 / S0012-365X (02) 00797-5, PAN  1485924.
  • belcastro, sarah-marie; Haas, Ruth (2015), „Trojúhelníkové jedinečné tříbarevné kubické grafy“, Příspěvky do diskrétní matematiky, 10 (2): 39–44, arXiv:1508.06934, Bibcode:2015arXiv150806934B, PAN  3499076.
  • Bollobás, Béla (1978), Extrémní teorie grafůMonografie LMS, 11Akademický tisk, PAN  0506522.
  • Fowler, Thomas (1998), Unikátní zbarvení rovinných grafů (PDF), Ph.D. diplomová práce, Gruzínský institut technické matematiky.
  • Hillar, Christopher J .; Windfeldt, Troels (2008), „Algebraická charakterizace jedinečně vrcholných barevných grafů“, Journal of Combinatorial Theory, Řada B, 98 (2): 400–414, arXiv:matematika / 0606565, doi:10.1016 / j.jctb.2007.08.004, PAN  2389606.
  • Mahmoodian, E. S .; Shokrollahi, M. A. (1995), „Otevřené problémy v kombinatorické dílně AIMC25 (Teherán, 1994)“, v C. J., Colbourn; E. S., Mahmoodian (eds.), Combinatorics Advances, Matematika a její aplikace, 329, Dordrecht; Boston; London: Kluwer Academic Publishers, s. 321–324.
  • Schwenk, Allen J. (1989), "Enumerace hamiltonovských cyklů v některých zobecněných Petersenových grafech", Journal of Combinatorial Theory, Řada B, 47 (1): 53–59, doi:10.1016/0095-8956(89)90064-6, PAN  1007713.
  • Thomason, A. G. (1978), „Hamiltonovské cykly a jedinečně zbarvitelné grafy hran“, Pokroky v teorii grafů (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, 3, str. 259–268, PAN  0499124.
  • Thomason, Andrew (1982), „Krychlové grafy se třemi hamiltonovskými cykly nejsou vždy jedinečně vybarvitelné od okraje“, Journal of Graph Theory, 6 (2): 219–221, doi:10,1002 / jgt.3190060218, PAN  0655209.
  • Truszczyński, M. (1984), „Some results on uniquely colourable graphs“, in Hajnal, A.; Lovász, L.; Sós, V. T. (eds.), Konečné a nekonečné sady. Sv. I, II. Sborník příspěvků ze šestého maďarského kombinatorického kolokvia konaného v Egeru 6. – 11. Července 1981Colloq. Matematika. Soc. János Bolyai, 37, Severní Holandsko, Amsterdam, str. 733–748, PAN  0818274.
  • Tutte, William T. (1976), „Hamiltonovské obvody“, Colloquio Internazionale sulle Teorie Combinatorie (Řím, 1973), Tomo I., Accad. Naz. Lincei, Řím, s. 193–199. Atti dei Convegni Lincei, č. 17, PAN  0480185. Jak uvádí belcastro & Haas (2015).
  • Xu, Shao Ji (1990), „Velikost jedinečně barevných grafů“, Journal of Combinatorial Theory, Řada B, 50 (2): 319–320, doi:10.1016 / 0095-8956 (90) 90086-F, PAN  1081235.
  • Wilson, R. J. (1976), "Problém 2", v Nash-Williams, C. St. J. A.; Sheehan, J. (eds.), Proc. British Comb. Konf. 1975, Winnipeg: Utilitas Math., Str. 696. Jak uvádí Thomason (1978).

externí odkazy