Id: arxiv/2606.25168 Url: https://arxiv.org/abs/2606.25168 Tags: math.CO Score: 0 Title: Star Coloring on Some Subclasses of Chordal Graphs Domain: math.CO Source: arxiv Authors: Germán Benítez-Bobadilla, Fernando Esteban Contreras-Mendoza, César Hernández-Cruz, Cláudia Linhares Sales, Ana Trujillo-Negrete Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-23 Page: https://delphi.science/r/arxiv/2606.25168 A star coloring of a graph $G$ is a proper coloring in which no path on four vertices is bicolored. The star chromatic number $χ_{\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…