Star coloring in graph theory - (correct) vertex coloring in which any path of four vertices uses at least three different colors. An equivalent definition is a coloring in which any connected components of the generated subgraphs formed by the vertices of any two colors are stars . Star coloring was proposed by Grünbaum [1] .
Star Chromatic Number count Is the minimum number of colors needed to get a star coloring .
One generalization of star coloring is closely related to the concept of acyclic coloring of a graph , which requires that any cycle use at least three colors, so that the subgraphs generated by a pair of colors form forests . Chromatic number of graph does not exceed stellar chromatic number , which actually means that any star coloring of the graph is acyclic coloring book.
It is proved that the stellar chromatic number is bounded for any minor closed class [2] . This result was later generalized [3] for all colorings with a shallow depth of trees (ordinary coloring and star coloring are coloring with a shallow depth of trees with parameters 1 and 2, respectively).
It was shown [4] that the verification of the inequality is an NP-complete problem , even if the graph at the same time both planar and dicotyledonous . Coleman and Moret [5] showed that the search for the optimal stellar coloring is NP-difficult , even if is a bipartite graph.
Notes
- ↑ Grunbaum, 1973 .
- ↑ Neshetrzhil, Osson, 2003 .
- ↑ Neshetrzhil, Osson, 2006 .
- ↑ Albertson, 2004 .
- ↑ Coleman, Moret, 1984 .
Literature
- Michael O. Albertson, Glenn G. Chappell, Hal A. Kierstead, André Kündgen, Radhika Ramamurthi. Coloring with no 2-Colored P 4 's // The Electronic Journal of Combinatorics. - 2004. - T. 11 , no. 1 . .
- Thomas F. Coleman, Jorge Moré. Estimation of sparse Hessian matrices and graph coloring problems // Mathematical Programming. - 1984. - T. 28 , no. 3 . - S. 243–270 . - DOI : 10.1007 / BF02612334 . .
- Guillaume Fertin, André Raspaud, Bruce Reed. Star coloring of graphs // Journal of Graph Theory. - 2004 .-- T. 47 , no. 3 . - S. 163–182 . - DOI : 10.1002 / jgt.20029 . .
- Branko Grünbaum. Acyclic colorings of planar graphs // Israel Journal of Mathematics. - 1973.- T. 14 . - S. 390–408 . - DOI : 10.1007 / BF02764716 . .
- Nešetřil Jaroslav, Ossona de Mendez Patrice. Discrete & Computational Geometry: The Goodman-Pollack Festschrift. - Springer-Verlag, 2003. - T. 25. - S. 651-664. - (Algorithms & Combinatorics). .
- Nešetřil Jaroslav, Ossona de Mendez Patrice. Tree depth, subgraph coloring and homomorphism bounds // European Journal of Combinatorics . - 2006. - T. 27 , no. 6 . - S. 1022-1041 . - DOI : 10.1016 / j.ejc.2005.01.010 . .
Links
- Star colorings and acyclic colorings (1973) , article on the Research Experiences for Graduate Students (REGS) website of the University of Illinois, 2008.