Star Extremal Circulant Graphs
Ko‐Wei Lih, Daphne Der‐Fen Liu, Xuding Zhu · SIAM Journal on Discrete Mathematics · 1999
A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number (also known as the star chromatic number). We prove that members of a certain family of circulant graphs are star extremal. The result generalizes some known theorems of Sidorenko [Discrete Math., 91 (1991), pp. 215--217] and Gao and Zhu [Discrete Math., 152 (1996), pp. 147--156]. We show relations between circulant graphs and distance graphs and discuss their star extremality. Furthermore, we give counterexamples to two conjectures of Collins [SIAM J. Discrete Math., 11 (1998), pp. 330--339] on asymptotic independence ratios of circulant graphs.