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 University Press

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

[1] Ajtai, M., Komlós, J., and Szemerédi, E., A note on Ramsey numbers . J. Combin. Theory Ser. A 29(1980), 354–360. . Google Scholar | DOI

[2] Bruhn, H. and Joos, F., A stronger bound for the strong chromatic index. arxiv:1504.02583. Google Scholar

[3] Cames Van Batenburg, W. and Kang, R. J., Squared chromatic number without claws or large cliques. arxiv:1609.08646. Google Scholar

[4] Chudnovsky, M. and Ovetsky, A., Coloring quasi-line graphs . J. Graph Theory 54(2007), no. 1, 41–50. . Google Scholar | DOI

[5] 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

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

[7] Chudnovsky, M. and Seymour, P., Claw-free graphs. VII. Quasi-line graphs . J. Combin. Theory Ser. B 102, no. 6, 1267–1294. . Google Scholar | DOI

[8] Chung, F. R. K., Gyárfás, A., Tuza, Z., and Trotter, W. T., The maximum number of edges in 2K -free graphs of bounded degree . Discrete Math. 81(1990), 129–135. . Google Scholar | DOI

[9] Edmonds, J., Paths, trees, and flowers . Canad. J. Math. 17(1965), 449–467. . Google Scholar | DOI

[10] Eisenbrand, F., Oriolo, G., Stauffer, G., and Ventura, P., The stable set polytope of quasi-line graphs . Combinatorica 28(2008), no. 1, 45–67. . Google Scholar | DOI

[11] 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

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

[13] Faenza, Y., Oriolo, G., and Stauffer, G., Solving the weighted stable set problem in claw-free graphs via decomposition . J. ACM 61(2014), no. 4, Art. 20, 41. . Google Scholar | DOI

[14] Gupta, R., The chromatic index and the degree of a graph . Notices Amer. Math. Soc. 13(1966), 719. Google Scholar

[15] Kierstead, H. A., Applications of edge coloring of multigraphs to vertex coloring of graphs . Discrete Math. 74(1989), no. 1–2, 117–124. . Google Scholar | DOI

[16] Kim, J. H., The Ramsey number R (3, t) has order of magnitude t 2/log t . Random Structures Algorithms 7(1995), 173–207. . Google Scholar | DOI

[17] King, A. D. and Reed, B., Asymptotics of the chromatic number for quasi-line graphs . J. Graph Theory 73(2013), 327–341. . Google Scholar | DOI

[18] King, A. D. and Reed, B., Claw-free graphs, skeletal graphs, and a stronger conjecture on 𝜔, 𝛥, and 𝜒 . J. Graph Theory 78(2015), 157–194. . Google Scholar | DOI

[19] Minty, G. J., On maximal independent sets of vertices in claw-free graphs . J. Combin. Theory Ser. B 28(1980), 284–304. . Google Scholar | DOI

[20] 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

[21] Nakamura, D. and Tamura, A., A revision of Minty’s algorithm for finding a maximum weight stable set of a claw-free graph . J. Oper. Res. Soc. Japan 44(2001), 194–204. . Google Scholar | DOI

[22] Sbihi, N., Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile . Discrete Math. 29(1980), 53–76. . Google Scholar | DOI

[23] Sumner, D. P., Subtrees of a graph and the chromatic number. In: The theory and applications of graphs (Kalamazoo, Mich., 1980), Wiley, New York, 1981, pp. 557–576. Google Scholar

[24] Vizing, V. G., On an estimate of the chromatic class of a p-graph. (Russian) . Diskret. Analiz No. 3(1964), 25–30. Google Scholar

Cité par Sources :