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.
机构:
King Khalid Univ, Coll Sci & Arts Majardah, Dept Math, Magardah 61937, Saudi ArabiaBahauddin Zakariya Univ, Ctr Adv Studies Pure & Appl Math, Multan 60800, Pakistan
Hilali, Shreefa O.
Alhagyan, Mohammed
论文数: 0引用数: 0
h-index: 0
机构:
Prince Sattam Bin Abdulaziz Univ, Coll Humanities & Sci Al Aflaj, Math Dept, Riyadh 11912, Saudi ArabiaBahauddin Zakariya Univ, Ctr Adv Studies Pure & Appl Math, Multan 60800, Pakistan
Alhagyan, Mohammed
Gargouri, Ameni
论文数: 0引用数: 0
h-index: 0
机构:
Prince Sattam Bin Abdulaziz Univ, Coll Humanities & Sci Al Aflaj, Math Dept, Riyadh 11912, Saudi ArabiaBahauddin Zakariya Univ, Ctr Adv Studies Pure & Appl Math, Multan 60800, Pakistan
机构:
Univ Carlos III Madrid, Dept Matemat, Ave Univ 30, Madrid 28911, SpainUniv Carlos III Madrid, Dept Matemat, Ave Univ 30, Madrid 28911, Spain
Rodriguez, Jose M.
Sigarreta, Jose M.
论文数: 0引用数: 0
h-index: 0
机构:
Univ Autonoma Guerrero, Fac Matemat, Carlos E Adame 54 Col Garita, Acalpulco 39650, Gro, MexicoUniv Carlos III Madrid, Dept Matemat, Ave Univ 30, Madrid 28911, Spain