Star Coloring on Some Subclasses of Chordal Graphs

Abstract

A star coloring of a graph $G$ is a proper coloring in which no path on four vertices is bicolored. The star chromatic number ${\chi }_{\star }(G)$ is the minimum number of colors in a star coloring of $G$. In this work we study star colorings from the perspective of forbidden induced subgraphs, focusing on three subclasses of chordal graphs. We provide both a structural characterization and a characterization in terms of forbidden induced subgraphs for star $3$-colorable chordal graphs; such characterizations yield a simple certifying recognition algorithm, running in time $O(|V|+|E|)$, for this class. We also characterize split graphs that are star $4$-colorable and star $5$-colorable in terms of (finitely many) forbidden induced subgraphs, again deriving linear-time certifying recognition algorithms. Finally, we study star colorings of $2$-trees and $2$-paths: we characterize the $2$-paths that are star $4$-colorable, prove that every $2$-path is star $5$-colorable, and exhibit a $2$-tree on $21$ vertices with star chromatic number $6$ such that any proper induced subgrahp has star chromatic number $5$.

39 pages, 19 figures