Geodesic
Squared Chromatic Number Without Claws or Large Cliques
Canadian mathematical bulletin, Tome 62 (2019) no. 1, pp. 23-35

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

Let $G$ be a claw-free graph on $n$ vertices with clique number $\unicode[STIX]{x1D714}$, and consider the chromatic number $\unicode[STIX]{x1D712}(G^{2})$ of the square $G^{2}$ of $G$. Writing $\unicode[STIX]{x1D712}_{s}^{\prime }(d)$ for the supremum of $\unicode[STIX]{x1D712}(L^{2})$ over the line graphs $L$ of simple graphs of maximum degree at most $d$, we prove that $\unicode[STIX]{x1D712}(G^{2})\leqslant \unicode[STIX]{x1D712}_{s}^{\prime }(\unicode[STIX]{x1D714})$ for $\unicode[STIX]{x1D714}\in \{3,4\}$. For $\unicode[STIX]{x1D714}=3$, this implies the sharp bound $\unicode[STIX]{x1D712}(G^{2})\leqslant 10$. For $\unicode[STIX]{x1D714}=4$, this implies $\unicode[STIX]{x1D712}(G^{2})\leqslant 22$, which is within 2 of the conjectured best bound. This work is motivated by a strengthened form of a conjecture of Erdős and Nešetřil.
DOI : 10.4153/CMB-2018-024-5
Mots-clés : graph colouring, Erdős–Nešetřil conjecture, claw-free graph 
Batenburg, Wouter Cames van; Kang, Ross J. Squared Chromatic Number Without Claws or Large Cliques. Canadian mathematical bulletin, Tome 62 (2019) no. 1, pp. 23-35. doi: 10.4153/CMB-2018-024-5
@article{10_4153_CMB_2018_024_5,
     author = {Batenburg, Wouter Cames van and Kang, Ross J.},
     title = {Squared {Chromatic} {Number} {Without} {Claws} or {Large} {Cliques}},
     journal = {Canadian mathematical bulletin},
     pages = {23--35},
     year = {2019},
     volume = {62},
     number = {1},
     doi = {10.4153/CMB-2018-024-5},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-2018-024-5/}
}
TY  - JOUR
AU  - Batenburg, Wouter Cames van
AU  - Kang, Ross J.
TI  - Squared Chromatic Number Without Claws or Large Cliques
JO  - Canadian mathematical bulletin
PY  - 2019
SP  - 23
EP  - 35
VL  - 62
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-2018-024-5/
DO  - 10.4153/CMB-2018-024-5
ID  - 10_4153_CMB_2018_024_5
ER  - 
%0 Journal Article
%A Batenburg, Wouter Cames van
%A Kang, Ross J.
%T Squared Chromatic Number Without Claws or Large Cliques
%J Canadian mathematical bulletin
%D 2019
%P 23-35
%V 62
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-2018-024-5/
%R 10.4153/CMB-2018-024-5
%F 10_4153_CMB_2018_024_5

[1] Andersen, L. D., The strong chromatic index of a cubic graph is at most 10. Topological, algebraical and combinatorial structures . Discrete Math. 108(1992), no. 1–3, 231–252., 1992. . Google Scholar | DOI

[2] Chudnovsky, M. and Seymour, P., The structure of claw-free graphs . In: Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., 327, Cambridge University Press, Cambridge, 2005, pp. 153–171. . Google Scholar | DOI

[3] Chudnovsky, M. and Seymour, P., Claw-free graphs VI. Colouring . J. Combin. Theory Ser. B 100(2010), 560–572. . Google Scholar | DOI

[4] Cranston, D. W., Strong edge-coloring of graphs with maximum degree 4 using 22 colors . Discrete Math. 306(2006), 2772–2778. . Google Scholar | DOI

[5] De Joannis De Verclos, R., Kang, R. J., and Pastor, L., Colouring squares of claw-free graphs . Canad. J. Math., to appear. . Google Scholar | DOI

[6] Erdős, P., Problems and results in combinatorial analysis and graph theory . In: Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), Discrete Math. 72(1988), 81–92. . Google Scholar | DOI

[7] Erdős, P. and Szekeres, G., A combinatorial problem in geometry . Compositio Math. 2(1935), 463–470. Google Scholar

[8] Horák, P., He, Q., and Trotter, W. T., Induced matchings in cubic graphs . J. Graph Theory 17(1993), 151–160. . Google Scholar | DOI

[9] Molloy, M. and Reed, B., A bound on the strong chromatic index of a graph . J. Combin. Theory Ser. B 69(1997), 103–109. . Google Scholar | DOI

Cité par Sources :