Star coloring

Short description: Graph coloring avoiding 2-colored paths

The star chromatic number of the Dyck graph is 4, although its chromatic number is 2.

In the mathematical field of graph theory, a star coloring of a graph G is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs.[1] Star coloring has been introduced by (Grünbaum 1973).[2] The star chromatic number χs(G) of G is the fewest colors needed to star color G.

## Contents

* 1 In special classes of graphs
* 2 Complexity
* 3 Related concepts
* 4 Notes
* 5 References
* 6 External links

## In special classes of graphs

(Grünbaum 1973) observed that the star chromatic number is bounded for planar graphs.[2] More precisely, the star chromatic number of planar graphs is at most 20, and some planar graphs have star chromatic number at least 10.[1] More generally, the star chromatic number is bounded on every proper minor closed class.[3] This result has been generalized to all low-tree-depth colorings (standard coloring and star coloring being low-tree-depth colorings with respective parameter 1 and 2).[4]

For every graph of maximum degree d, the star chromatic number is O(d3/2). There exist graphs for which this bound is close to tight: they have star chromatic number Ω(d3/2/log1/2n).[5]

## Complexity

It is NP-complete to determine whether χs(G)≤3, even when G is a graph that is both planar and bipartite.[1] Finding an optimal star coloring is NP-hard even when G is a bipartite graph.[6]

## Related concepts

Star coloring is the special case for q=3 of q-centered coloring, colorings in which every connected subgraph either uses at least q colors or has at least one color that is used for exactly one vertex. For such a coloring, a connected subgraph with only two colors must be a star, with the vertex of a unique color at its center. There can be no edges between the remaining vertices in the component, because they would form two-vertex connected subgraphs without a uniquely used color.[7]

Another generalization of star coloring is the closely related concept of acyclic coloring, where it is required that every cycle uses at least three colors, so the two-color induced subgraphs are forests. If we denote the acyclic chromatic number of a graph G by χa(G), we have that χa(G)≤χs(G), and in fact every star coloring of G is an acyclic coloring. In the other direction, χs(G)≤2χa(G)2−χa(G), so each of the two kinds of chromatic number is bounded if and only if the other one is.[1]

## Notes

1. ↑ 1.0 1.1 1.2 1.3 Albertson et al. (2004).
2. ↑ 2.0 2.1 Grünbaum (1973), p. 406, remark 12(i). harv error: no target: CITEREFGrünbaum1973 (help)
3. ↑ Nešetřil & Ossona de Mendez (2003). harv error: no target: CITEREFNešetřilOssona_de_Mendez2003 (help)
4. ↑ Nešetřil & Ossona de Mendez (2006). harv error: no target: CITEREFNešetřilOssona_de_Mendez2006 (help)
5. ↑ Fertin, Raspaud & Reed (2004). harv error: no target: CITEREFFertinRaspaudReed2004 (help)
6. ↑ Coleman & Moré (1984). harv error: no target: CITEREFColemanMoré1984 (help)
7. ↑ (Nešetřil Ossona de Mendez). The equivalence between the numbers denoted here as χp and the minimum number of colors in a (p+1)−centered coloring is (Nešetřil Ossona de Mendez).

## References

* Albertson, Michael O.; Chappell, Glenn G.; Kierstead, Hal A.; Kündgen, André; Ramamurthi, Radhika (2004), "Coloring with no 2-Colored P4's", The Electronic Journal of Combinatorics 11 (1), doi:10.37236/1779, http://www.combinatorics.org/Volume_11/Abstracts/v11i1r26.html .
* "Estimation of sparse Hessian matrices and graph coloring problems", Mathematical Programming 28 (3): 243–270, 1984, doi:10.1007/BF02612334, https://ecommons.cornell.edu/bitstream/1813/6374/1/82-535.pdf .
* Fertin, Guillaume; Raspaud, André (2004), "Star coloring of graphs", Journal of Graph Theory 47 (3): 163–182, doi:10.1002/jgt.20029, https://hal.archives-ouvertes.fr/hal-00307788 .
* "Acyclic colorings of planar graphs", Israel Journal of Mathematics 14 (4): 390–408, 1973, doi:10.1007/BF02764716 .
* "Colorings and homomorphisms of minor closed classes", Discrete & Computational Geometry: The Goodman-Pollack Festschrift, Algorithms & Combinatorics, 25, Springer-Verlag, 2003, pp. 651–664 .
* "Tree depth, subgraph coloring and homomorphism bounds", European Journal of Combinatorics 27 (6): 1022–1041, 2006, doi:10.1016/j.ejc.2005.01.010 .
* Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, 28, Springer, 2012, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7

## External links

* Star colorings and acyclic colorings (1973), present at the Research Experiences for Graduate Students (REGS) at the University of Illinois, 2008.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Star coloring. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Star_coloring&oldid=4230918"