Acyklické zbarvení grafu
V teorii grafů je acyklické zbarvení takové ( správné ) zbarvení vrcholu , ve kterém žádný dvoubarevný podgraf nemá žádné cykly .
Acyklické chromatické číslo A( G )
grafu G je nejmenší počet barev požadovaný pro jakékoli acyklické zbarvení G.
Acyklické zbarvení je často spojováno s grafy na nerovných površích.
Horní hranice
A ( g ) ≤ 2 a pouze tehdy, když G nemá cykly.
Hranice A( G ) z hlediska maximálního stupně Δ( G ) grafu G zahrnují následující:
- A( G ) ≤ 4, pokud Δ( G ) = 3. (Grünbaum 1973)
- A ( g ) ≤ 5, pokud Δ ( g ) = 4. (Burstein 1979)
- A( G ) ≤ 8, pokud Δ( G ) = 5.( Yadav, Satish 2008 )
- A( G ) ≤ 12, pokud Δ( G ) = 6.( Yadav, Satish 2009 )
Milníkem ve studiu acyklického zbarvení je následující kladná odpověď na Grünbaumovu domněnku:
Teorém. (Borodin 1979)
A( G ) ≤ 5, pokud je G rovinné.
Grünbaum (1973) zavedl acyklické zbarvení a acyklické chromatické číslo a učinil domněnku, kterou dokázal Borodin. Borodinovi trvalo několik let pečlivého ověřování 450 konfigurací, aby to dokázal. Jedním z důsledků této věty je, že jakýkoli rovinný graf lze rozložit na nezávislou množinu a dva lesy . (Stein 1970, 1971)
Algoritmy a složitost
Problém určení, zda platí A( G ) ≤ 3, je NP-úplný (Kostochka 1978). Coleman a Cai ( Coleman, Cai 1986 ) ukázali, že problém zůstává NP-úplný i pro bipartitní grafy.
Goebreedkhin et al. ( Gebremedhin, Tarafdar, Pothen, Walther 2008 ) prokázali, že každá správná horní malba akordického sloupce je acyklické zbarvení. Protože pro akordické grafy můžete najít optimální zbarvení pro O (N+M) , totéž platí pro aciciplastické zbarvení na této třídě grafů.
Časově lineární algoritmus pro acyklické vybarvování grafu maximálního stupně ≤ 3 do 4 barev nebo méně představuje Skulrattanakulchai ( Skulrattanakulchai 2004 ). Yadav a Satish ( Yadav, Satish 2008 ) popisují časově lineární acyklický algoritmus vybarvování grafu s maximálním stupněm ≤ 5 s použitím 8 barev nebo méně a také algoritmus pro vybarvování grafu s maximálním stupněm ≤ 6 s použitím 12 barev nebo méně.
Viz také
Poznámky
Odkazy
- MI Burstein. Každý 4-valentní graf má acyklické 5-zabarvení (v ruštině) // Soobšč. Akad. Nauk Gruzin. SSR. - 1979. - T. 93 . — S. 21–24 .
- B. Grunbaum. Acyklické obarvení rovinných grafů // Israel J. Math .. - 1973. - T. 14 . — S. 390–408 . - doi : 10.1007/BF02764716 .
- Thomas F. Coleman, Jin-Yi Cai. Problém cyklického zbarvení a odhad řídkých hessiánských matic // SIAM. J. o algebraických a diskrétních metodách. - 1986. - T. 7 . — S. 221–235 . - doi : 10.1137/0607026 . .
- Guillaume Fertin, André Raspaud. Acyklické barvení grafů maximálně pátého stupně: Devět barev stačí // Information Processing Letters. - 2008. - T. 105 . — S. 65–72 . - doi : 10.1016/j.ipl.2007.08.022 . .
- Kishore Yadav, Venkaiah Satish. Acyklické barvení grafů maximálně pátého stupně: Osm barev stačí // ICGTA. - 2008. - T. nula . - C. nula . .
- Kishore Yadav, Venkaiah Satish, Kishore Yadav, Kishore Kothapalli. Acyklické barvení grafů maximálně šestého stupně: Stačí dvanáct barev // Elektronické poznámky v diskrétní matematice. - 2009. - T. 35 . — S. 177–182 . - doi : 10.1016/j.endm.2009.11.030 . .
- Jensen, Tommy R.; Toft, BJARNE (1995). Problémy s barvením grafů . New York: Wiley-Interscience. ISBN 0-471-02865-7 .
- Kostochka, AV (1978). Horní hranice chromatických funkcí grafů (v ruštině). Doktorský asis, Novosibirsk.
- San Skulrattanakulchai. Acyklické zbarvení subkubických grafů // Information Processing Letters. - 2004. - T. 92 . — S. 161–167 . - doi : 10.1016/j.ipl.2004.08.002 . .
- SK Stein. B-množiny a problémy s barvením // Bull. amer. Matematika. Soc.. - 1970. - T. 76 . — S. 805–806 . - doi : 10.1090/S0002-9904-1970-12559-9 .
- SK Stein. B-množiny a rovinné mapy // Pacific J. Math .. - 1971. - T. 37 . — S. 217–224 .
Externí odkazy