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:

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

Külső linkek