Star chromatic numbers of graphs (Q2563519)

This paper investigates relations between the star chromatic number \(\chi^*(G)\) and the chromatic number \(\chi(G)\) of graphs \(G\). It is obvious that \(\chi(G)-1<\chi^*(G)\leq\chi(G)\). Two major parts of the paper are devoted to two opposite problems: (1) which graph \(G\) has the property that \(\chi^*(G)= \chi(G)\)? and (2) which graph \(G\) has the property that the star chromatic number \(\chi^*(G)\) is very close to \(\chi(G)-1\)? This paper proves a new sufficient condition for graphs having the first property (which is stronger than a few known results). As a direct corollary of the main theorem, every uniquely vertex \(\chi(G)\)-colorable graph \(G\) has the first property. For the second problem, this paper constructs an infinite family of graphs (\(\chi(G)\)-critical graphs) whose star chromatic numbers \(\chi^*(G)\) are arbitrarily close to \(\chi(G)-1\).