Teljes színezés

A gráfelméletben a teljes színezés a gráf csúcsainak és éleinek színezésének egy fajtája . Hacsak kifejezetten másként nem jelezzük, a teljes színezést helyesnek kell tekinteni abban az értelemben, hogy egyetlen szomszédos csúcs, illetve az élek végén fekvő szomszédos élek és csúcsok sincsenek azonos színnel színezve.

Egy G gráf teljes kromatikus száma χ″( G ) a legkisebb színszám, amely G teljes színezéséhez szükséges .

Egy G gráf T = T( G ) teljes gráfja olyan gráf, amelyben

  1. a T gráf csúcsainak halmaza megfelel a G gráf csúcsainak és éleinek ;
  2. T két csúcsa akkor és csak akkor szomszédos, ha a megfelelő elemek szomszédosak G -ben, vagy incidensek.

Ezzel a meghatározással a teljes színezés a teljes gráf (megfelelő) csúcsszínezésévé válik.

A χ″( G ) számos tulajdonsága :

  1. χ″( G ) ≥ Δ( G ) + 1.
  2. χ″( G ) ≤ Δ( G ) + 10 26 [1] .
  3. χ″( G ) ≤ Δ( G ) + 8 ln 8 (Δ( G )) kellően nagy Δ( G ) esetén [2] .
  4. χ″( G ) ≤ ch′( G ) + 2.

Itt Δ( G ) a maximális teljesítmény , ch′( G ) pedig az előírt élszínezés indexe .

A teljes színezés természetes módon jön létre, mivel ez a csúcs- és élszínezések egyszerű keveréke. A következő lépés a teljes kromatikus szám felső határának figyelembe vétele a maximális fokban, a Brooks- vagy a Vizing -tétel analógiájával . Kiderült, hogy a teljes színezés felső határának meghatározása a maximális fok függvényében nehéz feladat, és 40 éve elkerülte a matematikusokat.

A leghíresebb találgatás így hangzik:

Sejtés a teljes színezésről.

χ″( G ) ≤ Δ( G ) + 2.

Nyilvánvalóan a "teljes színezés" kifejezést és a sejtés megfogalmazását egymástól függetlenül javasolta Behzad és Vizing számos publikációjában 1964 és 1968 között (a részletekért lásd Jensen és Toft [3] könyvét ).

Ismeretes, hogy a sejtés a gráfok számos fontos osztályára érvényes, mint például a kétrészes gráfokra és a legtöbb síkgráfra , kivéve azokat a gráfokat, amelyek maximális foka 6. A síkgráfok esete megoldódik, ha Viizing síkgráf-sejtése igaznak bizonyult. Továbbá, ha az előírt élszínezésről szóló sejtés igaz, akkor χ″( G ) ≤ Δ( G ) + 3.

Kaptunk néhány eredményt a teljes színezéssel kapcsolatban. Például Kylakos és Read [4] bebizonyította, hogy a teljes gráf törtkromatikus indexe egy G gráf esetén nem haladja meg a Δ( G ) + 2 értéket.

Megemlítjük a következő kapcsolatot a vonalgráf és a teljes gráf között :

T ( G ) akkor és csak akkor Euler , ha L ( G ) Euler .

Jegyzetek

  1. ↑ Molloy, Reed, 1998 .
  2. ↑ Hind, Molloy, Reed, 1998 .
  3. ↑ Jensen, Toft, 1995 .
  4. ↑ Kilakos, Reed, 1993 .

Irodalom