Total farvelægning

I grafteori er en totalfarvning en form for farvning af spidserne og kanterne på en graf. Medmindre andet er udtrykkeligt angivet, antages en totalfarvning at være korrekt i den forstand, at ingen tilstødende spidser og ingen tilstødende kanter og spidser, der ligger i enderne af kanter, er farvet med samme farve.

Det samlede kromatiske tal χ″( G ) af en graf G er det mindste antal farver, der er nødvendigt for en samlet farvning af G .

En samlet graf T = T( G ) af en graf G er en graf, hvori

  1. sættet af toppunkter på grafen T svarer til toppunkter og kanter på grafen G ;
  2. to hjørner i T er tilstødende, hvis og kun hvis de tilsvarende elementer er enten nabostillede i G eller indfaldende.

Med denne definition bliver en totalfarvning til en (korrekt) vertexfarvning af en samlet graf.

Flere egenskaber ved χ″( G ):

  1. χ″( G ) ≥ Δ( G ) + 1.
  2. χ″( G ) ≤ Δ( G ) + 10 26 [1] .
  3. χ″( G ) ≤ Δ( G ) + 8 ln 8 (Δ( G )) for tilstrækkelig stor Δ( G ) [2] .
  4. χ″( G ) ≤ ch′( G ) + 2.

Her er Δ( G ) den maksimale effekt af , og ch′( G ) er indekset for den foreskrevne kantfarvning .

Totalfarvning opstår på en naturlig måde, da det er en simpel blanding af top- og kantfarver. Det næste trin er at overveje de øvre grænser for det samlede kromatiske tal i form af den maksimale grad, analogt med Brooks- eller Vizing- sætningerne . Det viste sig, at det er en vanskelig opgave at bestemme de øvre grænser for en total farvning som funktion af den maksimale grad og har undgået matematikere i 40 år.

Det mest berømte gæt lyder sådan her:

Formodning om total farvning.

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

Tilsyneladende blev udtrykket "total farvelægning" og formuleringen af ​​formodningen uafhængigt foreslået af Behzad og Vizing i adskillige publikationer mellem 1964 og 1968 (se bogen af ​​Jensen og Toft [3] for detaljer).

Formodningen er kendt for at holde for flere vigtige klasser af grafer, såsom todelte grafer og de fleste plane grafer , med undtagelse af grafer med en maksimal grad på 6. Tilfældet med plane grafer vil blive løst, hvis Vizings plane grafformodning er viste sig at være sandt. Hvis formodningen om den foreskrevne kantfarve er sand, så er χ″( G ) ≤ Δ( G ) + 3.

Nogle resultater vedrørende total farvning er opnået. For eksempel beviste Kylakos og Read [4] , at det kromatiske brøkindeks for den samlede graf for en graf G ikke overstiger Δ( G ) + 2.

Vi nævner også følgende sammenhæng mellem linjegrafen og den samlede graf :

T ( G ) er Euler , hvis og kun hvis L ( G ) er Euler .

Noter

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

Litteratur