Geodesic
Colouring Squares of Claw-free Graphs
Canadian journal of mathematics, Tome 71 (2019) no. 1, pp. 113-129

Voir la notice de l'article provenant de la source Cambridge

DOI

Is there some absolute $\unicode[STIX]{x1D700}>0$ such that for any claw-free graph $G$, the chromatic number of the square of $G$ satisfies $\unicode[STIX]{x1D712}(G^{2})\leqslant (2-\unicode[STIX]{x1D700})\unicode[STIX]{x1D714}(G)^{2}$, where $\unicode[STIX]{x1D714}(G)$ is the clique number of $G$? Erdős and Nešetřil asked this question for the specific case where $G$ is the line graph of a simple graph, and this was answered in the affirmative by Molloy and Reed. We show that the answer to the more general question is also yes, and, moreover, that it essentially reduces to the original question of Erdős and Nešetřil.
DOI : 10.4153/CJM-2017-029-9
Mots-clés : graph colouring, Erdős–Nešetřil conjecture, claw-free graphs 
Verclos, Rémi de Joannis de; Kang, Ross J.; Pastor, Lucas. Colouring Squares of Claw-free Graphs. Canadian journal of mathematics, Tome 71 (2019) no. 1, pp. 113-129. doi: 10.4153/CJM-2017-029-9
@article{10_4153_CJM_2017_029_9,
     author = {Verclos, R\'emi de Joannis de and Kang, Ross J. and Pastor, Lucas},
     title = {Colouring {Squares} of {Claw-free} {Graphs}},
     journal = {Canadian journal of mathematics},
     pages = {113--129},
     year = {2019},
     volume = {71},
     number = {1},
     doi = {10.4153/CJM-2017-029-9},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2017-029-9/}
}
TY  - JOUR
AU  - Verclos, Rémi de Joannis de
AU  - Kang, Ross J.
AU  - Pastor, Lucas
TI  - Colouring Squares of Claw-free Graphs
JO  - Canadian journal of mathematics
PY  - 2019
SP  - 113
EP  - 129
VL  - 71
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2017-029-9/
DO  - 10.4153/CJM-2017-029-9
ID  - 10_4153_CJM_2017_029_9
ER  - 
%0 Journal Article
%A Verclos, Rémi de Joannis de
%A Kang, Ross J.
%A Pastor, Lucas
%T Colouring Squares of Claw-free Graphs
%J Canadian journal of mathematics
%D 2019
%P 113-129
%V 71
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2017-029-9/
%R 10.4153/CJM-2017-029-9
%F 10_4153_CJM_2017_029_9

Cité par Sources :