Some star extremal circulant graphs
type: Item
instance of: scholarly article
title: Some star extremal circulant graphs
zbMATH Open document ID: 1023.05051
DOI: 10.1016/S0012-365X(02)00872-5
author: Wensong Lin
published in: Discrete Mathematics
publication date: 2003-09-25T00:00:00Z
review text: The circular chromatic number and the fractional chromatic number are two generalizations of the ordinary chromatic number of a graph \(G\). A graph is called star extremal if its circular chromatic number equals its fractional chromatic number. \textit{G. Gao} and \textit{X. Zhu} [Discrete Math. 152, 147-156 (1996; Zbl 0852.05046)], \textit{K.-W. Lih} et al. [SIAM J. Discrete Math. 12, 491-499 (1999; Zbl 0935.05042)] gave many classes of circulant graphs which are star extremal. In this paper the author studies the star extremality of circulant graphs whose generating sets are of the form \(\{1,2,\dots ,m-1,k,k+1,\dots ,k+m-2\}\), of the form \(\{k,k+1,\dots ,k'\}\), or of the form \(\{k,k+1,\dots ,k_{1},k_{2},k_{2}+1,\dots ,\lfloor p/2 \rfloor \}\), where \(p\) is the order of the graph. As a corollary, an improvement of a result of Gao and Zhu is proposed.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1985957
zbMATH Keywords: circular chromatic number
zbMATH Keywords: fractional chromatic number
zbMATH Keywords: circulant graph
zbMATH Keywords: star extremal graph
zbMATH Keywords: vertex transitive graph
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Homomorphisms of 3-chromatic graphs
cites work: A note on the star chromatic number
cites work: Q4736226
cites work: Circular chromatic numbers and fractional chromatic numbers of distance graphs
cites work: Circular chromatic numbers of Mycielski's graphs
cites work: Star-extremal graphs and the lexicographic product
cites work: Acyclic graph coloring and the complexity of the star chromatic number
cites work: The circular chromatic number of the Mycielskian ofGdk
cites work: Circular chromatic numbers of distance graphs with distance sets missing multiples
cites work: On the fractional chromatic number and the lexicographic product of graphs
cites work: The fractional chromatic number of mycielski's graphs
cites work: Star Extremal Circulant Graphs
cites work: Star chromatic numbers of graphs
cites work: Star chromatic number
cites work: Star chromatic numbers and products of graphs
cites work: Planar graphs with circular chromatic numbers between 3 and 4
cites work: Circular chromatic number and graph minors
cites work: Circular chromatic number: A survey
full work available at URL: s0012-365x(02)00872-5
OpenAlex ID: W2006518678
description: scientific article; zbMATH DE number 1985957