아세클릭 컬러링

그래프 이론에서, 악순환 색상은 모든 2색 서브그래프가 악순환인 (적절한) 정점 색이다.그래프 G의 A(G)는 G의 모든 Acyclic coloring에 필요한 가장 적은 색이다.

반복적인 색상은 종종 비 평면 표면에 포함된 그래프와 연관된다.

상한

A(G) ≤ G가 반복적인 경우에만 2가 된다.

G의 최대치인 Δ(G)의 관점에서 A(G)에 대한 경계는 다음을 포함한다.

• Δ(G) = 3. (그룬바움 1973)일 경우 A(G) ≤ 4
• A(G) Δ(G) = 4. (버스타인 1979년)
• A(G) Δ(G) = 5. (Kostochka & Stocker 2011)
• Δ(G) = 6. (Varagani 등)일 경우 A(G) ≤ 12. 2009)

순환색소 연구의 이정표는 그룬바움의 추측에 대한 다음과 같은 긍정적인 대답이다.

정리(Borodin 1979년) A(G) ≤ G가 평면 그래프인 경우 5.

그룬바움(1973)은 아큐리컬러컬러와 아큐리컬러컬러 수를 도입하였고, 그 결과를 위의 정리에서 추측하였다.보로딘의 증거는 450개의 환원 가능한 구성에 대한 수년간의 고된 검사를 포함했다.이 정리의 한 가지 결과는 모든 평면 그래프를 독립된 세트와 두 개의 유도 숲으로 분해할 수 있다는 것이다.(1970년, 1971년)

알고리즘 및 복잡성

A(G) ≤ 3. (Kostochka 1978)의 여부를 결정하는 것은 NP완료다.

콜먼&카이(1986)는 G가 초당적 그래프인 경우에도 문제의 의사결정 변종이 NP-완전하다는 것을 보여주었다.

게브레메딘 외 (2008) 화음 그래프의 모든 적절한 정점 색상은 또한 순환 색상이라는 것을 입증했다.코드 그래프는 O(n + m) 시간에 최적으로 색칠될 수 있으므로 해당 등급의 그래프에서 반복 색칠하는 경우에도 마찬가지다.

스컬라타나쿨차이(2004)는 4색 이하를 사용하여 최대도 33의 그래프를 반복적으로 색칠하는 선형 시간 알고리즘을 제공했다.

참고 항목

• 스타 컬러링

참조

• Borodin, O. V. (1979), "On acyclic colorings of planar graphs", Discrete Mathematics, 25 (3): 211–236, doi:10.1016/0012-365X(79)90077-3.
• Burstein, M. I. (1979), "Every 4-valent graph has an acyclic 5-coloring (in Russian)", Soobšč. Akad. Nauk Gruzin. SSR, 93: 21–24.
• Grünbaum, B. (1973), "Acyclic colorings of planar graphs", 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 Sparse Hessian Matrices" (PDF), SIAM Journal on Algebraic and Discrete Methods, 7 (2): 221–235, doi:10.1137/0607026, hdl:1813/6485.
• Fertin, Guillaume; Raspaud, André (2008), "Acyclic coloring of graphs of maximum degree five: Nine colors are enough", 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, Arijit; Pothen, Alex; Walther, Andrea (2008), "Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation", INFORMS Journal on Computing, 21 (2): 209–223, doi:10.1287/ijoc.1080.0286.
• Jensen, Tommy R.; Toft, Bjarne (1995), Graph Coloring Problems, New York: Wiley-Interscience, ISBN 978-0-471-02865-9.
• Kostochka, A. V. (1978), Upper bounds of chromatic functions of graphs, Doctoral thesis (in Russian), Novosibirsk.
• Kostochka, Alexandr V.; Stocker, Christopher (2011), "Graphs with maximum degree 5 are acyclically 7-colorable", Ars Mathematica Contemporanea, 4 (1): 153–164, doi:10.26493/1855-3974.198.541, MR 2785823.
• Skulrattanakulchai, San (2004), "Acyclic colorings of subcubic graphs", Information Processing Letters, 92 (4): 161–167, doi:10.1016/j.ipl.2004.08.002.
• Stein, S. K. (1970), "B-sets and coloring problems", Bulletin of the American Mathematical Society, 76 (4): 805–806, doi:10.1090/S0002-9904-1970-12559-9.
• Stein, S. K. (1971), "B-sets and planar maps", Pacific Journal of Mathematics, 37 (1): 217–224, doi:10.2140/pjm.1971.37.217.
• Varagani, Satish; Venkaiah, V. Ch.; Yadav, Kishore; Kothapalli, Kishore (2009), "Acyclic vertex coloring of graphs of maximum degree six", LAGOS'09 – Fifth Latin-American Algorithms, Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics, vol. 35, Elsevier, pp. 177–182, doi:10.1016/j.endm.2009.11.030, MR 2579427

외부 링크

• 2008년 일리노이 대학의 대학원생을 위한 연구 경험(REGS)에 제시된 별 색상과 반복 색상(1973)
• 최대도 그래프의 반복적 색채화 ∆, G가 제시한 토크 슬라이드.페르틴과 A.2005년 베를린 EUROCOMB 05에서 라스파우드.