Circular chromatic number of induced subgraphs of Kneser graphs

Meysam Alishahi, Ali Taherkhani


Investigating the equality of the chromatic number and the circular chromatic number of graphs has been an active stream of research for last decades. In this regard, Hajiabolhassan and Zhu in 2003 proved that if n is sufficiently large with respect to k, then the Schrijver graph SG(n, k) has the same chromatic and circular chromatic number. Later, Meunier in 2005 and independently, Simonyi and Tardos in 2006 proved that χ(SG(n, k)) = χc(SG(n, k)) if n is even. In this paper, we study the circular chromatic number of induced subgraphs of Kneser graphs. In this regard, we shall first generalize the preceding result to s-stable Kneser graphs for large even n and even s. Furthermore, as a generalization of the Hajiabolhassan-Zhu result, we prove that if n is large enough with respect to k, then any sufficiently large induced subgraph of the Kneser graph KG(n, k) has the same chromatic number and circular chromatic number.


Chromatic number, circular chromatic number, Kneser graph, stable Kneser graph

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications