Geodesic
Circular chromatic number of induced subgraphs of Kneser graphs
Ars Mathematica Contemporanea, Tome 15 (2018) no. 1, pp. 161-172.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.1296.5c7
Keywords: Chromatic number, circular chromatic number, Kneser graph, stable Kneser graph 
@article{10_26493_1855_3974_1296_5c7,
     author = {Meysam Alishahi and Ali Taherkhani},
     title = {Circular chromatic number of induced subgraphs of {Kneser} graphs},
     journal = {Ars Mathematica Contemporanea},
     pages = {161--172},
     publisher = {mathdoc},
     volume = {15},
     number = {1},
     year = {2018},
     doi = {10.26493/1855-3974.1296.5c7},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1296.5c7/}
}
TY  - JOUR
AU  - Meysam Alishahi
AU  - Ali Taherkhani
TI  - Circular chromatic number of induced subgraphs of Kneser graphs
JO  - Ars Mathematica Contemporanea
PY  - 2018
SP  - 161
EP  - 172
VL  - 15
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1296.5c7/
DO  - 10.26493/1855-3974.1296.5c7
LA  - en
ID  - 10_26493_1855_3974_1296_5c7
ER  - 
%0 Journal Article
%A Meysam Alishahi
%A Ali Taherkhani
%T Circular chromatic number of induced subgraphs of Kneser graphs
%J Ars Mathematica Contemporanea
%D 2018
%P 161-172
%V 15
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1296.5c7/
%R 10.26493/1855-3974.1296.5c7
%G en
%F 10_26493_1855_3974_1296_5c7
Meysam Alishahi; Ali Taherkhani. Circular chromatic number of induced subgraphs of Kneser graphs. Ars Mathematica Contemporanea, Tome 15 (2018) no. 1, pp. 161-172. doi : 10.26493/1855-3974.1296.5c7. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1296.5c7/

Cité par Sources :