Coloring with no 2-colored \(P_4\)'s
The electronic journal of combinatorics, Tome 11 (2004) no. 1
A proper coloring of the vertices of a graph is called a star coloring if every two color classes induce a star forest. Star colorings are a strengthening of acyclic colorings, i.e., proper colorings in which every two color classes induce a forest. We show that every acyclic $k$-coloring can be refined to a star coloring with at most $(2k^2-k)$ colors. Similarly, we prove that planar graphs have star colorings with at most 20 colors and we exhibit a planar graph which requires 10 colors. We prove several other structural and topological results for star colorings, such as: cubic graphs are $7$-colorable, and planar graphs of girth at least $7$ are $9$-colorable. We provide a short proof of the result of Fertin, Raspaud, and Reed that graphs with tree-width $t$ can be star colored with ${t+2\choose2}$ colors, and we show that this is best possible.
@article{10_37236_1779,
author = {Michael O. Albertson and Glenn G. Chappell and H. A. Kierstead and Andr\'e K\"undgen and Radhika Ramamurthi},
title = {Coloring with no 2-colored {\(P_4\)'s}},
journal = {The electronic journal of combinatorics},
year = {2004},
volume = {11},
number = {1},
doi = {10.37236/1779},
zbl = {1053.05045},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1779/}
}
TY - JOUR AU - Michael O. Albertson AU - Glenn G. Chappell AU - H. A. Kierstead AU - André Kündgen AU - Radhika Ramamurthi TI - Coloring with no 2-colored \(P_4\)'s JO - The electronic journal of combinatorics PY - 2004 VL - 11 IS - 1 UR - http://geodesic.mathdoc.fr/articles/10.37236/1779/ DO - 10.37236/1779 ID - 10_37236_1779 ER -
%0 Journal Article %A Michael O. Albertson %A Glenn G. Chappell %A H. A. Kierstead %A André Kündgen %A Radhika Ramamurthi %T Coloring with no 2-colored \(P_4\)'s %J The electronic journal of combinatorics %D 2004 %V 11 %N 1 %U http://geodesic.mathdoc.fr/articles/10.37236/1779/ %R 10.37236/1779 %F 10_37236_1779
Michael O. Albertson; Glenn G. Chappell; H. A. Kierstead; André Kündgen; Radhika Ramamurthi. Coloring with no 2-colored \(P_4\)'s. The electronic journal of combinatorics, Tome 11 (2004) no. 1. doi: 10.37236/1779
Cité par Sources :