| dbo:abstract
|
- 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 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) + 1026. (Molloy, Reed 1998) 3.
* χ″(G) ≤ Δ(G) + 8 ln8(Δ(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 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 (hu)
- 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 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) + 1026. (Molloy, Reed 1998) 3.
* χ″(G) ≤ Δ(G) + 8 ln8(Δ(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 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 (hu)
|
