스타 컬러링

Dyck 그래프의 항성 색수는 4이고, 색수는 2이다.

그래프-이론 수학에서 그래프 G의 항성 색상은 4개의 꼭지점의 모든 경로가 적어도 3개의 구별되는 색상을 사용하는 (적절한) 정점 색이다.마찬가지로, 항성 채색에서 어떤 두 가지 색상의 정점에 의해 형성된 유도 서브그래프는 항성 그래프인 구성요소를 연결했다.스타컬링은 그룬바움(1973년)에 의해 도입되었다.G의 항성 색수 $\chi {\displaystyle {}_{}}$ ${\displaystyle s_{}}$( ${\displaystyle G}$) ${\displaystyle \chi _{s}(G)}$는 G색을 항성하는 데 필요한 가장 적은 색이다.

스타 컬러링의 한 가지 일반화는 악순환 컬러링과 밀접하게 연관되어 있는 개념으로, 매 주기마다 최소 3가지 색상을 사용해야 하므로 2가지 색 유도 서브그래프는 숲이다.If we denote the acyclic chromatic number of a graph G by ${\displaystyle \chi _{a}(G)}$, we have that ${\displaystyle \chi _{a}(G)\leq \chi _{s}(G)}$, and in fact every star coloring of G is an acyclic coloring.

항성 색수는 네셰틸 & 오소나 데 멘데즈(2003)에 의해 모든 적절한 마이너 폐쇄 등급에 경계로 되어 있는 것으로 증명되었다.이러한 결과는 네셰틸&오소나 데 멘데스(2006)에 의해 모든 저나무 깊이 착색(표준 착색 및 별 착색은 각 매개변수 1과 2를 갖는 저나무 깊이 착색)으로 더욱 일반화되었다.

복잡성

그것은 알버트슨 외 연구진에 의해 증명되었다. (${\displaystyle \mathrm{2004}}$) G가 평면적이고 초당적인 그래프인 경우에도 ${\displaystyle \mathrm{even}}$ ${\displaystyle s_{}}$( G${\displaystyle }$) ${\displaystyle \le }$ 3 $[\displaystyle \chi _{s}(G)\leq 3$의 여부를 결정하는 것이 NP 완료라는 것.콜먼&모레(1984)는 G가 초당적 그래프인 경우에도 최적의 항성 채색성을 찾는 것이 NP-hard임을 보여줬다.

참조

• Albertson, Michael O.; Chappell, Glenn G.; Kierstead, Hal A.; Kündgen, André; Ramamurthi, Radhika (2004), "Coloring with no 2-Colored P₄'s", The Electronic Journal of Combinatorics, 11 (1), MR 2056078.
• Coleman, Thomas F.; Moré, Jorge (1984), "Estimation of sparse Hessian matrices and graph coloring problems" (PDF), Mathematical Programming, 28 (3): 243–270, doi:10.1007/BF02612334, hdl:1813/6374, MR 0736293.
• Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory, 47 (3): 163–182, doi:10.1002/jgt.20029, MR 2089462.
• Grünbaum, Branko (1973), "Acyclic colorings of planar graphs", Israel Journal of Mathematics, 14: 390–408, doi:10.1007/BF02764716, MR 0317982.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2003), "Colorings and homomorphisms of minor closed classes", Discrete & Computational Geometry: The Goodman-Pollack Festschrift, Algorithms & Combinatorics, vol. 25, Springer-Verlag, pp. 651–664, MR 2038495.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2006), "Tree depth, subgraph coloring and homomorphism bounds", European Journal of Combinatorics, 27 (6): 1022–1041, doi:10.1016/j.ejc.2005.01.010, MR 2226435.

외부 링크

• 2008년 일리노이 대학의 대학원생을 위한 연구 경험(REGS)에 제시된 별 색상과 반복 색상(1973)