Egyedülállóan színezhető grafikon

Az egyedülállóan színezhető gráf egy k-színű gráf, amely csak egy (helyes) k színezést engedélyez (a színek permutációjáig).

Példák

Egy teljes gráf egyedileg színezhető, mert csak egy érvényes színezés létezik – minden csúcshoz más szín van hozzárendelve.

Bármely k - fa egyedileg színezhető ( k  + 1) színekkel. A 4 színnel egyedileg színezhető síkgráfok pontosan Apollonius gráfok , azaz sík 3 fák [ 1] .

Tulajdonságok

Egy egyedileg k színezhető , n csúcsú és m élű G gráf néhány tulajdonsága :

  1. m ≥ ( k - 1) n - k ( k -1)/2 [2] [3]

Kapcsolódó fogalmak

Minimális tökéletlenség

A minimálisan tökéletlen gráf olyan gráf, amelyben minden részgráf tökéletes . A minimálisan tökéletlen gráf bármely csúcsának eltávolítása egyedi színezhető részgráfot eredményez.

Egyértékű élszínezés

Egy egyedülállóan vonallal színezhető gráf egy k - él - színes gráf , amely csak egy (helyes) k - él színezést engedélyez a színek permutációjáig. Csak az utak és ciklusok engednek egyértékű 2-él színezést. Bármely k értéke esetén a K 1, k csillagok egyedileg k -él színezhető gráfok. Wilson [4] azonban előadott egy sejtést, és Thomason [5] bebizonyította, hogy k ≥ 4 esetén ezek a család egyetlen tagjai. Vannak azonban egyedülállóan 3 éllel színezhető gráfok, amelyek nem tartoznak ebbe az osztályozásba, például a háromszög alakú piramisgráf .

Ha egy köbös gráf egyedileg 3 élben színezhető, akkor pontosan három Hamilton-ciklussal kell rendelkeznie, amelyeket két (három) szín élei alkotnak, de néhány csak három Hamilton-ciklust tartalmazó köbös gráfnak nincs egyedi 3 élszínezése. [6] . Bármely egyszerű sík köbös gráf, amely egyedi 3 élszínezést tesz lehetővé, tartalmaz egy háromszöget [1] , de Tut [7] észrevette, hogy a G (9,2) általánosított Petersen-gráf egy nem sík háromszög nélküli gráf, de ez egyedileg 3 élesen színezhető. Sok éven át ez a gráf volt az egyetlen példa ilyen gráfokra (lásd Bolobash [8] és Schwenk [9] írásait ), de ma már végtelenül sok nem sík háromszög nélküli köbös gráf létezik, amelyeknek egyértékű 3 élük van. -színezés [6] .

Egy-egy teljes színezés

Az egyedülállóan teljesen színezhető gráf egy teljesen k színű gráf , amely csak egy (helyes) teljes k színezést engedélyez (a színek permutációjáig).

Az üres gráfok , az utak ésa 3-mal osztható ciklusok egyedi, teljesen színezhető gráfok. Mahmudian és Shokrollahi [10] azt sejtette, hogy csak ezek a grafikonok alkotják a családot.

Egy egyedi, teljesen k színezhető , n csúcsú G gráf néhány tulajdonsága :

  1. χ″( G ) = Δ( G ) + 1, hacsak G = K 2 [11]
  2. Δ( G ) ≤ 2 δ( G ). [tizenegy]
  3. Δ( G ) ≤ n/2 + 1. [12]

Itt χ″( G ) a teljes kromatikus szám ; Δ( G ) a maximális fok és δ( G ) a minimális fok.

Jegyzetek

  1. ↑ 12 Fowler , 1998 .
  2. ↑ Truszczyński, 1984 .
  3. ↑ Xu, 1990 .
  4. ↑ Wilson, 1976 .
  5. ↑ Thomason, 1978 .
  6. ↑ 1 2 Belcastro, Haas, 2015 .
  7. ↑ Tutte, 1976 .
  8. ↑ Bollobás, 1978 .
  9. ↑ Schwenk, 1989 .
  10. ↑ Mahmoodian, Shokrollahi, 1995 .
  11. ↑ 1 2 Akbari, Behzad, Hajiabolhassan, Mahmoodian, 1997 .
  12. ↑ Akbari, 2003 .

Irodalom

Linkek