Aciklikus grafikon színezés
A gráfelméletben az aciklikus színezés egy (megfelelő) csúcsszínezés , amelyben bármely kétszínű részgráfnak nincsenek ciklusai .
A G gráf A( G ) aciklikus kromatikus száma a legkisebb színszám, amely a G aciklikus színezéshez szükséges .
Az aciklikus színezés gyakran nem sík felületeken lévő grafikonokhoz kapcsolódik.
Felső határok
A( G ) ≤ 2 akkor és csak akkor, ha G -nek nincsenek ciklusai.
Az A( G ) határai a G gráf Δ( G ) maximális fokára vonatkoztatva a következőket tartalmazzák:
- A( G ) ≤ 4, ha Δ( G ) = 3. (Grünbaum 1973)
- A( G ) ≤ 5, ha Δ( G ) = 4. (Burstein 1979)
- A( G ) ≤ 8, ha Δ( G ) = 5. ( Yadav, Satish 2008 )
- A( G ) ≤ 12, ha Δ( G ) = 6. ( Yadav, Satish 2009 )
Az aciklikus színezés tanulmányozásának mérföldköve a következő pozitív válasz Grünbaum sejtésére:
Tétel. (Borodin 1979)
A( G ) ≤ 5, ha G sík.
Grünbaum (1973) egy aciklikus színezést és egy aciklikus kromatikus számot vezetett be, és egy sejtést tett, amit Borodin igazolt. Borodinnak több évre volt szüksége 450 konfiguráció szorgalmas ellenőrzésére, hogy ezt bizonyítsa. Ennek a tételnek az egyik következménye, hogy bármely síkgráf felbontható egy független halmazra és két erdőre . (Stein 1970, 1971)
Algoritmusok és összetettség
Az A( G ) ≤ 3 teljesülésének a problémája NP-teljes (Kostochka 1978). Coleman és Cai ( Coleman, Cai 1986 ) kimutatták, hogy a probléma még kétrészes gráfok esetén is NP-teljes marad.
Gebremedhin és munkatársai ( Gebremedhin, Tarafdar, Pothen, Walther 2008 ) kimutatták, hogy egy akkordgráf bármely megfelelő csúcsszínezése aciklikus színezés. Mivel lehetséges az akkordgráfok optimális színezése O(n+m) idő alatt, ugyanez igaz az aciklikus színezésre ezen a gráfosztályon.
Skulrattanakulchai ( Skulrattanakulchai 2004 ) egy idő-lineáris algoritmust mutat be egy maximum ≤ 3-as fokú gráf 4 vagy annál kisebb színre való aciklikus színezésére . Yadav és Satish ( Yadav, Satish 2008 ) egy idő-lineáris aciklikus gráfszínezési algoritmust ír le, amelynek maximális foka ≤ 5 8 vagy annál kevesebb szín használatával, valamint egy algoritmust, amely maximum ≤ 6 fokú gráfot 12 vagy kevesebb szín használatával színez.
Lásd még
Jegyzetek
Linkek
- MI Burstein. Minden 4 vegyértékű gráfnak van egy aciklikus 5 színezése (oroszul) // Soobšč. Akad. Nauk Gruzin. SSR. - 1979. - T. 93 . – S. 21–24 .
- B. Grunbaum. Síkgráfok aciklikus színezése // Israel J. Math .. - 1973. - T. 14 . – S. 390–408 . - doi : 10.1007/BF02764716 .
- Thomas F. Coleman, Jin-Yi Cai. A ciklikus színezési probléma és a ritka Hess-mátrixok becslése // SIAM. J. az algebrai és diszkrét módszerekről. - 1986. - T. 7 . – S. 221–235 . - doi : 10.1137/0607026 . .
- Guillaume Fertin, André Raspaud. Maximum ötös fokú grafikonok aciklikus színezése: Kilenc szín elég // Information Processing Letters. - 2008. - T. 105 . – S. 65–72 . - doi : 10.1016/j.ipl.2007.08.022 . .
- Kishore Yadav, Venkaiah Satish. Maximum ötös fokú grafikonok aciklikus színezése: Nyolc szín elég // ICGTA. - 2008. - T. nil . - C. nulla . .
- Kishore Yadav, Venkaiah Satish, Kishore Yadav, Kishore Kothapalli. Maximum hatos fokú gráfok aciklikus színezése: Tizenkét szín elég // Electronic Notes in Discrete Mathematics. - 2009. - T. 35 . – S. 177–182 . - doi : 10.1016/j.endm.2009.11.030 . .
- Assefaw H. Gebremedhin, Arijit Tarafdar, Alex Pothen, Andrea Walther. A ritka hessenek hatékony számítása színezéssel és automatikus megkülönböztetéssel // Informs Journal on Computing. - 2008. - T. 21 . - S. 209 . - doi : 10.1287/ijoc.1080.0286 . .
- Jensen, Tommy R.; Toft, Bjarne (1995). Grafikonszínezési problémák . New York: Wiley-Interscience. ISBN 0-471-02865-7 .
- Kostochka, A. V. (1978). Gráfok kromatikus függvényeinek felső határai (oroszul). Doktori értekezés, Novoszibirszk.
- San Skulrattanakulchai. Szubkubikus gráfok aciklikus színezése // Információfeldolgozási levelek. - 2004. - T. 92 . – S. 161–167 . - doi : 10.1016/j.ipl.2004.08.002 . .
- SK Stein. B-készletek és színezési problémák // Bull. amer. Math. Szoc.. - 1970. - T. 76 . – S. 805–806 . - doi : 10.1090/S0002-9904-1970-12559-9 .
- SK Stein. B-halmazok és síktérképek // Pacific J. Math .. - 1971. - T. 37 . – S. 217–224 .
Külső linkek