Colorarea graficului aciclic

În teoria grafurilor, o colorare aciclică este o colorare a vârfurilor (corectă) în care orice subgraf cu două culori nu are cicluri . Numărul cromatic aciclic A( G ) al unui grafic G este cel mai mic număr de culori necesare în orice colorare aciclică G.

Colorarea aciclică este adesea asociată cu grafice pe suprafețe neplane.

Limite superioare

A( G ) ≤ 2 dacă și numai dacă G nu are cicluri.

Limitele lui A( G ) în ceea ce privește gradul maxim Δ( G ) al graficului G includ următoarele:

• A( G ) ≤ 4 dacă Δ( G ) = 3. (Grünbaum 1973)
• A( G ) ≤ 5 dacă Δ( G ) = 4. (Burstein 1979)
• A( G ) ≤ 8 dacă Δ( G ) = 5.( Yadav, Satish 2008 )
• A( G ) ≤ 12 dacă Δ( G ) = 6.( Yadav, Satish 2009 )

O piatră de hotar în studiul colorării aciclice este următorul răspuns pozitiv la conjectura lui Grünbaum:

Teorema. (Borodin 1979)

Grünbaum (1973) a introdus o colorare aciclică și un număr cromatic aciclic și a făcut o presupunere, care a fost demonstrată de Borodin. Borodin a avut nevoie de câțiva ani de verificare diligentă a 450 de configurații pentru a dovedi acest lucru. O consecință a acestei teoreme este că orice graf plan poate fi descompus într- o mulțime independentă și două păduri . (Stein 1970, 1971)

Algoritmi și complexitate

Problema determinării dacă A( G ) ≤ 3 este valabilă este NP-complet (Kostochka 1978). Coleman și Cai ( Coleman, Cai 1986 ) au arătat că problema rămâne NP-completă chiar și pentru grafurile bipartite.

Gebremedhin și colaboratorii ( Gebremedhin, Tarafdar, Pothen, Walther 2008 ) au demonstrat că orice colorare adecvată a nodurilor a unui graf cordal este o colorare aciclică. Deoarece este posibil să se găsească o colorare optimă pentru grafurile cordale în timp O(n+m) , același lucru este valabil și pentru o colorare aciclică pe această clasă de grafuri.

Un algoritm liniar în timp pentru colorarea aciclică a unui grafic de grad maxim ≤ 3 în 4 culori sau mai puțin este prezentat de Skullrattanakulchai ( Skullrattanakulchai 2004 ). Yadav și Satish ( Yadav, Satish 2008 ) descriu un algoritm de colorare a graficului aciclic liniar în timp cu gradul maxim ≤ 5 folosind 8 culori sau mai puțin, precum și un algoritm pentru colorarea unui grafic cu gradul maxim ≤ 6 folosind 12 culori sau mai puțin.

Vezi și

• carte de colorat stea

Note

Link -uri

• OV Borodin. Despre colorațiile aciclice ale grafurilor plane // Matematică discretă . - 1979. - T. 25 . — S. 211–236 . - doi : 10.1016/0012-365X(79)90077-3 . .

• MI Burstein. Fiecare grafic cu 4 valențe are un 5-colorare aciclic (în rusă) // Soobšč. Akad. Nauk Gruzin. SSR. - 1979. - T. 93 . — S. 21–24 .
• B. Grunbaum. Colorări aciclice ale grafurilor plane // Israel J. Math .. - 1973. - T. 14 . — S. 390–408 . - doi : 10.1007/BF02764716 .

• Thomas F. Coleman, Jin-Yi Cai. Problema de colorare ciclică și estimarea matricilor hessiene rare // SIAM. J. despre metode algebrice şi discrete. - 1986. - T. 7 . — S. 221–235 . - doi : 10.1137/0607026 . .

• Guillaume Fertin, André Raspaud. Colorarea aciclică a graficelor de gradul maxim cinci: Sunt suficiente nouă culori // Litere de procesare a informațiilor. - 2008. - T. 105 . — S. 65–72 . - doi : 10.1016/j.ipl.2007.08.022 . .

• Kishore Yadav, Venkaiah Satish. Colorarea aciclică a graficelor de gradul maxim cinci: Opt culori sunt suficiente // ICGTA. - 2008. - T. nil . - C. nul . .
• Kishore Yadav, Venkaiah Satish, Kishore Yadav, Kishore Kothapalli. Colorarea aciclică a graficelor de gradul maxim șase: Douăsprezece culori sunt suficiente // Note electronice la matematică discretă. - 2009. - T. 35 . — S. 177–182 . - doi : 10.1016/j.endm.2009.11.030 . .

• Assefaw H. Gebremedhin, Arijit Tarafdar, Alex Pothen, Andrea Walther. Calcularea eficientă a hessianelor rare folosind colorarea și diferențierea automată // informează Journal on Computing. - 2008. - T. 21 . - S. 209 . - doi : 10.1287/ijoc.1080.0286 . .

• Jensen, Tommy R.; Toft, Bjarne (1995). Probleme de colorare a graficelor . New York: Wiley-Interscience. ISBN 0-471-02865-7 .
• Kostochka, A.V. (1978). Limitele superioare ale funcțiilor cromatice ale graficelor (în rusă). Teză de doctorat, Novosibirsk.

• San Skullrattanakulchai. Colorări aciclice ale graficelor subcubice // Litere de procesare a informațiilor. - 2004. - T. 92 . — S. 161–167 . - doi : 10.1016/j.ipl.2004.08.002 . .

• SK Stein. B-seturi și probleme de colorare // Bull. amer. Matematică. Soc.. - 1970. - T. 76 . — S. 805–806 . - doi : 10.1090/S0002-9904-1970-12559-9 .
• SK Stein. B-seturi și hărți plane // Pacific J. Math .. - 1971. - T. 37 . — S. 217–224 .

Link- uri externe

• Star colorings and acyclic colorings (1973) , prezent la Research Experiences for Graduate Students (REGS) de la Universitatea din Illinois, 2008.
• Acyclic Coloring of Graphs of Maximum Degree ∆ , diapozitive prezentate de G. Fertin și A. Raspaud la EUROCOMB 05, Berlin, 2005.