Circular chromatic number of induced subgraphs of Kneser graphs

preprint2016arXivOpen access

Abstract

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, Habolhassan and Zhu [Circular chromatic number of Kneser graphs, Journal of Combinatorial Theory Series B, 2003] proved that if nn is sufficiently large with respect to kk, then the Schrijver graph SG(n,k){\rm SG}(n,k) has the same chromatic and circular chromatic number. Later, Meunier [A topological lower bound for the circular chromatic number of Schrijver graphs, Journal of Graph Theory, 2005] and independently, Simonyi and Tardos [ Local chromatic number, Ky Fan's theorem and circular colorings, Combinatorica, 2006] proved that χ(SG(n,k))=χc(SG(n,k))χ({\rm SG}(n,k))=χ_c({\rm SG}(n,k)) if nn 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 ss-stable Kneser graphs. Furthermore, as a generalization of Hajiabolhassan and Zhu's result, we prove that if nn is large enough with respect to kk, then any sufficiently large induced subgraph of the Kneser graph KG(n,k){\rm KG}(n,k) has the same chromatic number and circular chromatic number.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.