Acyklisk graffarvning
I grafteori er en acyklisk farvning en (korrekt) toppunktfarvning , hvor enhver tofarvet undergraf ikke har nogen cyklusser .
Det acykliske kromatiske tal A( G ) af en graf G er det mindste antal farver, der kræves i enhver acyklisk farvning G .
Acyklisk farvning er ofte forbundet med grafer på ikke-plane overflader.
Øvre grænser
A( G ) ≤ 2 hvis og kun hvis G ikke har nogen cyklusser.
Grænserne for A( G ) i form af den maksimale grad Δ( G ) af grafen G inkluderer følgende:
- A( G ) ≤ 4 hvis Δ( G ) = 3. (Grünbaum 1973)
- A( G ) ≤ 5 hvis Δ( G ) = 4. (Burstein 1979)
- A( G ) ≤ 8 hvis Δ( G ) = 5.( Yadav, Satish 2008 )
- A( G ) ≤ 12 hvis Δ( G ) = 6.( Yadav, Satish 2009 )
En milepæl i studiet af acyklisk farvning er følgende positive svar på Grünbaums formodning:
Sætning. (Borodin 1979)
A( G ) ≤ 5 hvis G er plan.
Grünbaum (1973) introducerede en acyklisk farve og et acyklisk kromatisk tal og fremsatte en formodning, som blev bevist af Borodin. Det tog Borodin flere år med flittig verifikation af 450 konfigurationer for at bevise det. En konsekvens af denne sætning er, at enhver plan graf kan dekomponeres i et uafhængigt sæt og to skove . (Stein 1970, 1971)
Algoritmer og kompleksitet
Problemet med at afgøre, om A( G ) ≤ 3 holder, er NP-komplet (Kostochka 1978). Coleman og Cai ( Coleman, Cai 1986 ) viste, at problemet forbliver NP-komplet selv for todelte grafer.
Gebremedhin et al. ( Gebremedhin, Tarafdar, Pothen, Walther 2008 ) påviste, at enhver korrekt vertexfarvning af en kordegraf er en acyklisk farvning. Da det er muligt at finde en optimal farvning for akkordegrafer i O(n+m) tid, gælder det samme for en acyklisk farvning på denne klasse af grafer.
En tids-lineær algoritme for acyklisk farvning af en graf med maksimal grad ≤ 3 til 4 farver eller mindre præsenteres af Skulrattanakulchai ( Skulrattanakulchai 2004 ). Yadav og Satish ( Yadav, Satish 2008 ) beskriver en tidslineær acyklisk graffarvealgoritme med maksimal grad ≤ 5 ved brug af 8 farver eller mindre, samt en algoritme til farvning af en graf med maksimal grad ≤ 6 ved brug af 12 farver eller mindre.
Se også
Noter
Links
- MI Burstein. Hver 4-valent graf har en acyklisk 5-farve (på russisk) // Soobšč. Akad. Nauk Gruzin. SSR. - 1979. - T. 93 . — S. 21–24 .
- B. Grunbaum. Acykliske farvninger af plane grafer // Israel J. Math .. - 1973. - T. 14 . — S. 390–408 . - doi : 10.1007/BF02764716 .
- Thomas F. Coleman, Jin-Yi Cai. Det cykliske farveproblem og estimering af sparsomme hessiske matricer // SIAM. J. om algebraiske og diskrete metoder. - 1986. - T. 7 . — S. 221–235 . - doi : 10.1137/0607026 . .
- Guillaume Fertin, André Raspaud. Acyklisk farvning af grafer med maksimal grad fem: Ni farver er nok // Information Processing Letters. - 2008. - T. 105 . — S. 65–72 . - doi : 10.1016/j.ipl.2007.08.022 . .
- Kishore Yadav, Venkaiah Satish. Acyklisk farvning af grafer med maksimal grad fem: Otte farver er nok // ICGTA. - 2008. - T. nul . - C. nul . .
- Kishore Yadav, Venkaiah Satish, Kishore Yadav, Kishore Kothapalli. Acyklisk farvning af grafer med maksimal grad seks: Tolv farver er nok // Elektroniske noter i diskret matematik. - 2009. - T. 35 . — S. 177–182 . - doi : 10.1016/j.endm.2009.11.030 . .
- Assefaw H. Gebremedhin, Arijit Tarafdar, Alex Pothen, Andrea Walther. Effektiv beregning af sparsomme hessianere ved hjælp af farvelægning og automatisk differentiering // Informerer Journal on Computing. - 2008. - T. 21 . - S. 209 . - doi : 10.1287/ijoc.1080.0286 . .
- Jensen, Tommy R.; Toft, Bjarne (1995). Problemer med graffarve . New York: Wiley-Interscience. ISBN 0-471-02865-7 .
- Kostochka, A.V. (1978). Øvre grænser for kromatiske funktioner af grafer (på russisk). Doktorafhandling, Novosibirsk.
- San Skulrattanakulchai. Acykliske farvninger af subkubiske grafer // Informationsbehandlingsbreve. - 2004. - T. 92 . — S. 161–167 . - doi : 10.1016/j.ipl.2004.08.002 . .
- SK Stein. B-sæt og farveproblemer // Bull. amer. Matematik. Soc.. - 1970. - T. 76 . — S. 805–806 . - doi : 10.1090/S0002-9904-1970-12559-9 .
- SK Stein. B-sæt og plankort // Pacific J. Math .. - 1971. - T. 37 . — S. 217–224 .
Eksterne links