Geodesic
Chi-Boundedness of graphs containing no cycles with k chords
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e189

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

We prove that the family of graphs containing no cycle with exactly k-chords is $\chi $-bounded, for k large enough or of form $\ell (\ell -2)$ with $\ell \ge 3$ an integer. This verifies (up to a finite number of values k) a conjecture of Aboulker and Bousquet (2015). 
Lee, Joonkyung; Letzter, Shoham; Pokrovskiy, Alexey. Chi-Boundedness of graphs containing no cycles with k chords. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e189. doi: 10.1017/fms.2025.10120
@article{10_1017_fms_2025_10120,
     author = {Lee, Joonkyung and Letzter, Shoham and Pokrovskiy, Alexey},
     title = {Chi-Boundedness of graphs containing no cycles with k chords},
     journal = {Forum of Mathematics, Sigma},
     pages = {e189},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.10120},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10120/}
}
TY  - JOUR
AU  - Lee, Joonkyung
AU  - Letzter, Shoham
AU  - Pokrovskiy, Alexey
TI  - Chi-Boundedness of graphs containing no cycles with k chords
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e189
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10120/
DO  - 10.1017/fms.2025.10120
ID  - 10_1017_fms_2025_10120
ER  - 
%0 Journal Article
%A Lee, Joonkyung
%A Letzter, Shoham
%A Pokrovskiy, Alexey
%T Chi-Boundedness of graphs containing no cycles with k chords
%J Forum of Mathematics, Sigma
%D 2025
%P e189
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10120/
%R 10.1017/fms.2025.10120
%F 10_1017_fms_2025_10120

[1] Aboulker, P. and Bousquet, N., ‘Excluding cycles with a fixed number of chords’, Discr. Appl. Math. 180 (2015), 11–24.10.1016/j.dam.2014.08.006 Google Scholar | DOI

[2] Bollobás, B. and Thomason, A., ‘Highly linked graphs’, Combinatorica 16 (1996), 313–320.10.1007/BF01261316 Google Scholar | DOI

[3] Bousquet, N. and Thomassé, S., ‘On the chromatic number of wheel-free graphs with no large bipartite graphs’, preprint (2015). Google Scholar

[4] Chalpion, J., Esperet, L., Li, Z. and Ossona De Mendez, P., ‘Restricted frame graphs and a conjecture of Scott’, Electron. J. Combin. 23 (2016), P 1.30. Google Scholar

[5] Davies, J., ‘Triangle-free graphs with large chromatic number and no induced wheel’, J. Graph Theory 103 (2023), no. 1, 112–118.10.1002/jgt.22906 Google Scholar | DOI

[6] Erdős, P., ‘Graph theory and probability’, Canad. J. Math. 11 (1959), 34–38.10.4153/CJM-1959-003-9 Google Scholar | DOI

[7] Gyárfás, A., ‘On Ramsey covering-numbers’, Infinite and Finite Sets 2 (1975), 801–816. Google Scholar

[8] Gyárfás, A., ‘Problems from the world surrounding perfect graphs’, Applicationes Math. 19 (1987), 413–441.10.4064/am-19-3-4-413-441 Google Scholar | DOI

[9] Kierstead, H. A. and Penrice, S. G., ‘Radius two trees specify -bounded classes’, J. Graph Theory 18(2) (1994), 119–129.10.1002/jgt.3190180203 Google Scholar | DOI

[10] Kierstead, H. A. and Zhu, Y., ‘Radius three trees in graphs with large chromatic number’, SIAM J. Discr. Math. 17 (2004), 571–581.10.1137/S0895480198339869 Google Scholar | DOI

[11] Kühn, D. and Osthus, D., ‘Induced subdivisions in -free graphs of large average degree’, Combinatorica 24 (2004), 287–304.10.1007/s00493-004-0017-8 Google Scholar | DOI

[12] Kóvari, T., Sós, V. and Turán, P., ‘On a problem of K. Zarankiewicz’, Colloq. Math. 3 (1954), 50–57.10.4064/cm-3-1-50-57 Google Scholar | DOI

[13] Mycielski, J., ‘Sur le coloriage des graphes’, Colloq. Math. 3 (1955), 161–162.10.4064/cm-3-2-161-162 Google Scholar | DOI

[14] Pawlik, A., Kozik, J., Krawczyk, T., Lasoń, M., Micek, P., Trotter, W. T. and Walczak, B., ‘Triangle-free intersection graphs of line segments with large chromatic number’, J. Combin. Theory Ser. B 105 (2014), 6–10.10.1016/j.jctb.2013.11.001 Google Scholar | DOI

[15] Scott, A. D., ‘Induced trees in graphs of large chromatic number’, J. Graph Theory 24 (1997), 297–311.10.1002/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.0.CO;2-J Google Scholar | DOI

[16] Sumner, D. P., ‘Subtrees of a graph and chromatic number’, in The Theory and Applications of Graphs (John Wiley & Sons, New York, 1981), 557–576. Google Scholar

[17] Thomas, R. and Wollan, P., ‘An improved linear edge bound for graph linkages’, European J. Combin. 26 (2005), 309–324.10.1016/j.ejc.2004.02.013 Google Scholar | DOI

[18] Trotignon, N., ‘Perfect graphs: a survey’, preprint (2013), . Google Scholar | arXiv

[19] Trotignon, N. and Vušković, K., ‘A structure theorem for graphs with no cycle with a unique chord and its consequences’, J. Graph Theory 63 (2010), 31–67.10.1002/jgt.20405 Google Scholar | DOI

Cité par Sources :