Star extremal circulant graphs

Citation
Kw. Lih et al., Star extremal circulant graphs, SIAM J DISC, 12(4), 1999, pp. 491-499
Citations number
22
Categorie Soggetti
Engineering Mathematics
Journal title
SIAM JOURNAL ON DISCRETE MATHEMATICS
ISSN journal
08954801 → ACNP
Volume
12
Issue
4
Year of publication
1999
Pages
491 - 499
Database
ISI
SICI code
0895-4801(1999)12:4<491:SECG>2.0.ZU;2-K
Abstract
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 ex tremal. The result generalizes some known theorems of Sidorenko [Discrete M ath., 91 (1991), pp. 215-217] and Gao and Zhu [Discrete Math., 152 (1996), pp. 147-156]. We show relations between circulant graphs and distance graph s and discuss their star extremality. Furthermore, we give counterexamples to two conjectures of Collins [SIAM J. Discrete Math., 11 (1998), pp. 330-3 39] on asymptotic independence ratios of circulant graphs.