Totális színezés
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.[1])
A totális színezés megegyezik a totális gráf jó színezésével.
χ″(G) néhány tulajdonsága:
- χ″(G) ≥ Δ(G) + 1.
- χ″(G) ≤ Δ(G) + 1026. (Molloy, Reed 1998)
- χ″(G) ≤ Δ(G) + 8 ln8(Δ(G)) elegendően nagy Δ(G)-re. (Hind, Molloy, Reed 1998)
- χ″(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 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:
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[szerkeszté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[szerkesztés]
- ↑ (Harary 1972), p. 82.
- (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.