Totális színezés

A $K_{4}$ teljes gráf totális színezése

A matematika, azon belül a gráfelmélet területén egy gráf totális színezése (total coloring) a gráfszínezések olyan fajtája, amikor a gráf csúcsai és élei is színt kapnak. Ha külön nem jelölik, mindig a gráf „jó” totális színezéséről van szó, tehát sem érintkező élek, sem valamely él végpontjai nem lehetnek azonos színűek. Egy G gráf χ″(G) totális kromatikus száma a G totális színezéséhez szükséges legkevesebb szín száma. A totális színezés a gráfot totális független csúcshalmazokra particionálja.

Egy G gráfhoz tartozó T = T(G) totális gráf az a gráf, melynek (i) csúcshalmaza megfelel G csúcsainak és éleinek (ii) két csúcs pontosan akkor szomszédos T-ben, ha a nekik megfelelő elemek szomszédosak vagy illeszkednek G-ben. (A totális gráf megkapható úgy is, ha G minden élét felbontjuk, majd a felbontott gráfot második hatványra emeljük.)

A totális színezés megegyezik a totális gráf jó színezésével.

χ″(G) néhány tulajdonsága:

1. χ″(G) ≥ Δ(G) + 1.
2. χ″(G) ≤ Δ(G) + 10²⁶. (Molloy, Reed 1998)
3. χ″(G) ≤ Δ(G) + 8 ln⁸(Δ(G)) elegendően nagy Δ(G)-re. (Hind, Molloy, Reed 1998)
4. χ″(G) ≤ ch′(G) + 2.

Δ(G) a maximális fokszám, ch′(G) pedig a lista-élkromatikus szám.

A totális színezés természetes módon adja magát a csúcs- és élszínezések egyesítéséből. A következő logikus lépés a Brooks- vagy Vizing-típusú felső korlátok keresése a totális kromatikus számra a maximális fokszám függvényében.

Mint kiderült, ez utóbbi probléma olyan nehéz, hogy több mint 40 éve nem boldogulnak vele a matematikusok. Triviálisan belátható, hogy a totális kromatikus szám nem lehet kisebb a maximális fokszám + 1, azaz Δ(G) + 1-nél (ezeket Class 1 gráfnak nevezik), néhány gráftípus esetében pedig (mint a hárommal nem osztható hosszúságú körök, és a $K_{n,n}$ alakú teljes páros gráfok) Δ(G) + 2 színre van szükség. Nem sikerült azonban olyan gráfra bukkanni, ahol a Δ(G) + 2 szín ne lenne elegendő. Ezért a következő sejtést állították fel, mely szerint csak az említett két gráfosztály létezik a totális színezés szempontjából:

Foster-cage totális színezése 6 színnel. A gráf totális kromatikus száma 6, mivel minden csúcs fokszáma 5 (5 szomszédos él + 1 csúcs = 6).

Totális színezési sejtés (Behzad, Vizing)

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

A „total coloring” kifejezést és a totális színezési sejtést egymástól függetlenül Behzad és Vizing használták elsőként több alkalommal 1964 és 1968 között. (Részletek: [Jensen, Toft 1995].)

A sejtést néhány fontos gráfcsaládra sikerült igazolni, köztük az összes páros gráfra, azokra a síkbarajzolható gráfokra melyek minimális fokszáma nem 6, illetve azokra a síkbarajzolható gráfokra, melyekben egyetlen 5 vagy 6 fokszámú csúcs sem fekszik háromnál több 3-körön.

A síkbarajzolható gráfok teljességére a sejtés igazsága következik, amennyiben Vizing síkbarajzolható gráfokra vonatkozó sejtése igaz. Továbbá, ha a listaszínezési sejtés igaz, akkor χ″(G) ≤ Δ(G) + 3.

Néhány totális színezéssel kapcsolatos eredmény:

Kilakos and Reed (1993) bizonyították, hogy G gráf totális gráfjának frakcionális kromatikus száma legfeljebb Δ(G) + 2.

A totális gráf élgráfjával kapcsolatos eredmény:

T = T(G) pontosan akkor rendelkezik Euler-körrel, ha az L(G) élgráf is rendelkezik vele.

Fordítás

• Ez a szócikk részben vagy egészben a Total coloring című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• (1998) „Total coloring with Δ + poly(logΔ) colors”. SIAM Journal on Computing 28 (3), 816–821. o. DOI:10.1137/S0097539795294578. 
• Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
• (1993) „Fractionally colouring total graphs”. Combinatorica 13 (4), 435–440. o. DOI:10.1007/BF01303515. 
• (1998) „A bound on the total chromatic number”. Combinatorica 18 (2), 241–280. o. DOI:10.1007/PL00009820. 
• Harary, F. (1972), "8. Line Graphs", Graph Theory, Massachusetts: Addison-Wesley, pp. 71–83, <http://www.dtic.mil/dtic/tr/fulltext/u2/705364.pdf>. Hozzáférés ideje: 2018-03-16 Archiválva 2017. február 7-i dátummal a Wayback Machine-ben.

További információk

• Maxfield Edwin Leidner, University of Louisville: A study of the total coloring of graphs doi:10.18297/etd/815