Jedinečně vybarvitelný graf

Jednoznačně vybarvitelný graf je k-barevný graf, který připouští pouze jedno (správné) k - zabarvení (až do permutace barev).

Příklady

Celý graf je jedinečně vybarvitelný, protože existuje pouze jedno platné zabarvení – každému vrcholu je přiřazena jiná barva.

Jakýkoli k - strom je jedinečně vybarvitelný pomocí ( k  + 1) barev. Rovinné grafy , které jsou jednoznačně vybarvitelné 4 barvami , jsou přesně Apolloniovy grafy , tedy rovinné 3-stromy [1] .

Vlastnosti

Některé vlastnosti jednoznačně k -obarvitelného grafu G s n vrcholy a m hranami:

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

Související pojmy

Minimální nedokonalost

Minimálně nedokonalý graf je graf, ve kterém je každý podgraf dokonalý . Odstraněním jakéhokoli vrcholu z minimálně nedokonalého grafu zůstane jedinečně vybarvitelný podgraf.

Jednohodnotové zbarvení hran

Jednoznačně čárově obarvitelný graf je graf obarvený k hraně , který připouští pouze jedno (správné) obarvení k -hran až do permutace barev. Pouze stezky a cykly připouštějí jednohodnotové zbarvení 2 hran. Pro libovolnou hodnotu k jsou hvězdy K 1, k jednoznačně k -hranově vybarvitelné grafy. Wilson [4] však předložil domněnku a Thomason [5] dokázal, že pro k ≥ 4 jsou to jediní členové této rodiny. Existují však jednoznačně 3hranné vybarvitelné grafy, které do této klasifikace nespadají, jako je trojúhelníkový pyramidový graf .

Pokud je kubický graf jednoznačně obarvitelný na 3 hranách, musí mít přesně tři hamiltonovské cykly tvořené hranami dvou (ze tří) barev, ale některé kubické grafy s pouze třemi hamiltonovskými cykly nemají jedinečné zbarvení 3 hran. [6] . Jakýkoli jednoduchý rovinný kubický graf připouštějící jedinečné zabarvení 3 hran obsahuje trojúhelník [1] , ale Tut [7] si všiml, že zobecněný Petersenův graf G (9,2) je nerovinný graf bez trojúhelníků, ale je jedinečně 3hranné obarvitelné. Po mnoho let byl tento graf jediným příkladem takových grafů (viz práce Bolobashe [8] a Schwenka [9] ), ale nyní existuje nekonečně mnoho nerovinných kubických grafů bez trojúhelníků, které mají jednohodnotové 3-hrany -barvení [6] .

Jednobarevné plné vybarvení

Jedinečně zcela vybarvitelný graf je zcela k -barevný graf , který připouští pouze jedno (správné) celkové k -zabarvení (až do permutace barev).

Prázdné grafy , cesty a cykly s délkou dělitelnou 3 jsou jednoznačně zcela vybarvitelné grafy. Mahmudian a Shokrollahi [10] předpokládali, že pouze tyto grafy tvoří rodinu.

Některé vlastnosti jednoznačně totálně k -obarvitelného grafu G s n vrcholy:

  1. χ″( G ) = Δ( G ) + 1, pokud G = K 2 [11]
  2. Δ( G ) ≤ 2 5( G ). [jedenáct]
  3. Δ( G ) ≤ n/2 + 1. [12]

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

Poznámky

  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 .

Literatura

Odkazy