Asiklik renklendirme - Acyclic coloring

McGee grafiğinin asiklik kromatik sayısı 3'tür.

Olarak grafik teorisi , bir asiklik boyama a, (uygun) köşe boyama her hangi 2-renk alt grafiğinin bir asiklik . Asiklik renk sayısı A ( G bir grafik) G herhangi asiklik boyama gerekli en az renkler G .

Asiklik renklendirme genellikle düzlem olmayan yüzeylere gömülü grafiklerle ilişkilendirilir.

Üst sınırlar

A( G ) ≤ 2 ancak ve ancak G asiklik ise.

A( G ) üzerindeki sınırlar , G'nin maksimum derecesi olan Δ( G ) cinsinden aşağıdakileri içerir:

Asiklik renklendirme çalışmasında bir dönüm noktası, Grünbaum'un bir varsayımına aşağıdaki olumlu cevaptır:

Teorem ( Borodin 1979 ) A( G ) ≤ 5 eğer G düzlemsel grafik ise.

Grünbaum (1973) , asiklik renklendirme ve asiklik kromatik sayıyı tanıttı ve sonucu yukarıdaki teoremde tahmin etti. Borodin'in kanıtı, 450 indirgenebilir konfigürasyonun birkaç yıl süren özenli denetimini içeriyordu. Bu teoremin bir sonucu, her düzlemsel grafiğin bağımsız bir kümeye ve iki indüklenmiş ormana ayrıştırılabilmesidir . (Stein  1970 , 1971 )

Algoritmalar ve karmaşıklık

İse NP-tam belirlemek için olup bir ( G ≤ 3 () 1978 Kostochka )

Coleman ve Cai (1986) , G iki parçalı bir grafik olduğunda bile problemin karar varyantının NP-tam olduğunu gösterdi .

Gebremedhin et al. (2008) , bir kordal grafiğin her uygun köşe renginin aynı zamanda bir asiklik renklendirme olduğunu göstermiştir. Kordal grafikler O( n + m ) zamanında en uygun şekilde renklendirilebildiğinden , aynı şey o grafik sınıfındaki asiklik renklendirme için de geçerlidir.

Skulrattanakulchai (2004) tarafından 4 veya daha az renk kullanarak maksimum derece ≤ 3 olan bir grafiği döngüsel olmayan bir şekilde renklendirmek için bir doğrusal zaman algoritması verildi .

Ayrıca bakınız

Referanslar

  • Borodin, OV (1979), "Düzlemsel grafiklerin asiklik renklendirmeleri üzerine", Discrete Mathematics , 25 (3): 211–236, doi : 10.1016/0012-365X(79)90077-3.
  • Burstein, MI (1979), "Her 4 değerli grafiğin asiklik bir 5 rengi vardır (Rusça)", Soobšč. Akad. Nauk Gruzin. SSR , 93 : 21–24.
  • Grünbaum, B. (1973), "Düzlemsel grafiklerin asiklik renklendirmeleri", Israel Journal of Mathematics , 14 (4): 390–408, doi : 10.1007/BF02764716
  • Coleman, Thomas F.; Cai, Jin-Yi (1986), "The Cyclic Coloring Problem and Estimation of Seyrek Hessian Matris" (PDF) , SIAM Journal on Algebraic and Discrete Methods , 7 (2): 221–235, doi : 10.1137/0607026 , hdl : 1813/6485.
  • Fertin, Guillaume; Raspaud, André (2008), "En yüksek dereceli grafiklerin döngüsel olmayan renklendirilmesi: Dokuz renk yeterlidir", Information Processing Letters , 105 (2): 65–72, CiteSeerX  10.1.1.78.5369 , doi : 10.1016/j.ipl .2007.08.022.
  • Gebremedhin, Assefaw H.; Tarafdar, Arıjit; Poten, Alex; Walther, Andrea (2008), "Renklendirme ve Otomatik Farklılaşma Kullanarak Seyrek Hessenlerin Verimli Hesaplanması", INFORMS Journal on Computing , 21 (2) : 209–223 , doi : 10.1287/ijoc.1080.0286.
  • Jensen, Tommy R.; Toft, Bjarne (1995), Grafik Renklendirme Problemleri , New York: Wiley-Interscience, ISBN 978-0-471-02865-9.
  • Kostochka, AV (1978), Grafiklerin kromatik fonksiyonlarının üst sınırları , Doktora tezi (Rusça), Novosibirsk.
  • Kostochka, Alexandr V.; Stocker, Christopher (2011), "Maksimum derece 5 olan grafikler çevrimsiz olarak 7 renklendirilebilir" , Ars Mathematica Contemporanea , 4 (1): 153–164, doi : 10.26493/1855-3974.198.541 , MR  2785823.
  • Skulrattanakulchai, San (2004), "Subkübik grafiklerin asiklik renklendirmeleri", Information Processing Letters , 92 (4): 161–167, doi : 10.1016/j.ipl.2004.08.002.
  • Stein, SK (1970), "B-kümeleri ve renklendirme problemleri", Amerikan Matematik Derneği Bülteni , 76 (4): 805-806 , doi : 10.1090/S0002-9904-1970-12559-9 .
  • Stein, SK (1971), "B-kümeleri ve düzlemsel haritalar", Pacific Journal of Mathematics , 37 (1) : 217–224 , doi : 10.2140/pjm.1971.37.217 .
  • Varagani, Satiş; Venkaiah, V. Ch.; Yadav, Kishore; Kothapalli, Kishore (2009), "En yüksek derece altı grafiklerin asiklik tepe noktası renklendirmesi", LAGOS'09 – Beşinci Latin-Amerika Algoritmaları, Grafikler ve Optimizasyon Sempozyumu , Ayrık Matematikte Elektronik Notlar, 35 , Elsevier, s. 177–182, doi : 10.1016/j.endm.2009.11.030 , MR  2579427

Dış bağlantılar