Polynomial Gyárfás–Sumner conjecture for graphs of bounded boxicity

Davies, James; Yuditsky, Yelena

doi:10.5802/igt.17

¹University of Leipzig, Faculty of Mathematics and Computer Science, Augustusplatz 10, 04109 Leipzig, Germany
²Université libre de Bruxelles, Computer Science Department, Campus de la Plaine, Boulevard du Triomphe B-1050, Brussels, Belgium

Innovations in Graph Theory, Volume 3 (2026), pp. 37-48

Abstract

We prove that for every positive integer $d$ and forest $F$, the class of intersection graphs of axis-aligned boxes in $\mathbb{R}^d$ with no induced $F$ subgraph is (polynomially) $\chi $-bounded.

Received: 2024-09-18
Accepted: 2025-12-10
Published online: 2026-04-02

DOI: 10.5802/igt.17

Classification: 05C15, 05C62
Keywords: Gyárfás–Sumner conjecture, $F$-free graphs for a forest $F$, graph coloring, bounded boxicity

Author's affiliations:

Davies, James ¹ ; Yuditsky, Yelena ²

¹ University of Leipzig, Faculty of Mathematics and Computer Science, Augustusplatz 10, 04109 Leipzig, Germany
² Université libre de Bruxelles, Computer Science Department, Campus de la Plaine, Boulevard du Triomphe B-1050, Brussels, Belgium

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{IGT_2026__3__37_0,
     author = {Davies, James and Yuditsky, Yelena},
     title = {Polynomial {Gy\'arf\'as{\textendash}Sumner} conjecture for graphs of bounded boxicity},
     journal = {Innovations in Graph Theory},
     pages = {37--48},
     year = {2026},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {3},
     doi = {10.5802/igt.17},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.17/}
}

TY  - JOUR
AU  - Davies, James
AU  - Yuditsky, Yelena
TI  - Polynomial Gyárfás–Sumner conjecture for graphs of bounded boxicity
JO  - Innovations in Graph Theory
PY  - 2026
SP  - 37
EP  - 48
VL  - 3
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.17/
DO  - 10.5802/igt.17
LA  - en
ID  - IGT_2026__3__37_0
ER  -

%0 Journal Article
%A Davies, James
%A Yuditsky, Yelena
%T Polynomial Gyárfás–Sumner conjecture for graphs of bounded boxicity
%J Innovations in Graph Theory
%D 2026
%P 37-48
%V 3
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.17/
%R 10.5802/igt.17
%G en
%F IGT_2026__3__37_0

Davies, James; Yuditsky, Yelena. Polynomial Gyárfás–Sumner conjecture for graphs of bounded boxicity. Innovations in Graph Theory, Volume 3 (2026), pp. 37-48. doi: 10.5802/igt.17

References
Cited by

[1] Asplund, E.; Grünbaum, B. On a coloring problem, Math. Scand., Volume 8 (1960), pp. 181-188 | DOI | MR | Zbl

[2] Bollobás, Béla Colouring lattices, Algebra Univers., Volume 7 (1977) no. 3, pp. 313-314 | DOI | MR | Zbl

[3] Briański, Marcin; Davies, James; Walczak, Bartosz Separating polynomial $χ$ -boundedness from $χ$ -boundedness, Combinatorica, Volume 44 (2024) no. 1, pp. 1-8 | DOI | MR | Zbl

[4] Burling, James P. On coloring problems of families of polytopes, Ph. D. Thesis, University of Colorado (1965) | DOI | MR

[5] Chalermsook, Parinya; Walczak, Bartosz Coloring and maximum weight independent set of rectangles, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics (2021), pp. 860-868 | DOI | MR | Zbl

[6] Chudnovsky, Maria; Cook, Linda; Davies, James; Oum, Sang-il Reuniting $χ$ -boundedness with polynomial $χ$ -boundedness, J. Comb. Theory, Ser. B, Volume 176 (2026), pp. 30-73 | DOI | MR | Zbl

[7] Chudnovsky, Maria; Scott, Alex; Seymour, Paul Induced subgraphs of graphs with large chromatic number. XII. Distant stars, J. Graph Theory, Volume 92 (2019) no. 3, pp. 237-254 | DOI | MR | Zbl

[8] Chudnovsky, Maria; Scott, Alex; Seymour, Paul Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings, J. Comb. Theory, Ser. B, Volume 150 (2021), pp. 195-243 | DOI | MR | Zbl

[9] Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie Polynomial bounds for chromatic number VI. Adding a four-vertex path, Eur. J. Comb., Volume 110 (2023), Paper no. 103710, 10 pages | DOI | MR | Zbl

[10] Davies, James Box and segment intersection graphs with large girth and chromatic number, Adv. Comb., Volume 2021 (2021), Paper no. 7, 9 pages | DOI | MR | Zbl

[11] Davies, James Improved bounds for colouring circle graphs, Proc. Am. Math. Soc., Volume 150 (2022) no. 12, pp. 5121-5135 | DOI | MR | Zbl

[12] Davies, James; Keller, Chaya; Kleist, Linda; Smorodinsky, Shakhar; Walczak, Bartosz A solution to Ringel’s circle problem, 38th International Symposium on Computational Geometry (LIPIcs – Leibniz International Proceedings in Informatics), Volume 224, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022 article no. 33 (14 pages) | DOI | MR | Zbl

[13] Davies, James; Krawczyk, Tomasz; McCarty, Rose; Walczak, Bartosz Coloring polygon visibility graphs and their generalizations, J. Comb. Theory, Ser. B, Volume 161 (2023), pp. 268-300 | DOI | MR | Zbl

[14] Davies, James; Krawczyk, Tomasz; McCarty, Rose; Walczak, Bartosz Grounded L-graphs are polynomially $χ$ -bounded, Discrete Comput. Geom., Volume 70 (2023) no. 4, pp. 1523-1550 | DOI | MR | Zbl

[15] Davies, James; McCarty, Rose Circle graphs are quadratically $χ$ -bounded, Bull. Lond. Math. Soc., Volume 53 (2021) no. 3, pp. 673-679 | DOI | MR | Zbl

[16] Descartes, Blanche A three colour problem, Eureka, Volume 9 (1947) no. 21, pp. 24-25

[17] Descartes, Blanche Solution to advanced problem no. 4526, Am. Math. Mon., Volume 61 (1954) no. 352, p. 216

[18] Erdős, Paul Graph theory and probability, Can. J. Math., Volume 11 (1959), pp. 34-38 | DOI | MR | Zbl

[19] Gyárfás, A. On Ramsey covering-numbers, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III (Colloquia Mathematica Societatis János Bolyai), North-Holland, 1975 no. 10, pp. 801-816 | MR | Zbl

[20] Gyárfás, A. Problems from the world surrounding perfect graphs, Zastos. Mat., Volume 19 (1987) no. 3-4, pp. 413-441 | MR | Zbl

[21] Gyárfás, A.; Szemerédi, E.; Tuza, Zs. Induced subtrees in graphs of large chromatic number, Discrete Math., Volume 30 (1980) no. 3, pp. 235-244 | DOI | MR | Zbl

[22] Károlyi, Gy. On point covers of parallel rectangles, Period. Math. Hung., Volume 23 (1991) no. 2, pp. 105-107 | DOI | MR | Zbl

[23] Kierstead, H. A.; Penrice, S. G. Radius two trees specify $χ$ -bounded classes, J. Graph Theory, Volume 18 (1994) no. 2, pp. 119-129 | DOI | MR | Zbl

[24] Kierstead, H. A.; Rodl, V. Applications of hypergraph coloring to coloring graphs not inducing certain trees, Discrete Math., Volume 150 (1996) no. 1-3, pp. 187-193 Selected papers in honour of Paul Erdős on the occasion of his 80th birthday (Keszthely, 1993) | DOI | MR | Zbl

[25] Kierstead, H. A.; Zhu, Yingxian Radius three trees in graphs with large chromatic number, SIAM J. Discrete Math., Volume 17 (2004) no. 4, pp. 571-581 | DOI | MR | Zbl

[26] Kostochka, A. V.; Nešetřil, J. Coloring relatives of intervals on the plane. I. Chromatic number versus girth, Eur. J. Comb., Volume 19 (1998) no. 1, pp. 103-110 | DOI | MR | Zbl

[27] Liu, Xiaonan; Schroeder, Joshua; Wang, Zhiyu; Yu, Xingxing Polynomial $χ$ -binding functions for $t$ -broom-free graphs, J. Comb. Theory, Ser. B, Volume 162 (2023), pp. 118-133 | DOI | MR | Zbl

[28] Middendorf, Matthias; Pfeiffer, Frank Weakly transitive orientations, Hasse diagrams and string graphs, Discrete Math., Volume 111 (1993) no. 1-3, pp. 393-400 Graph theory and combinatorics (Marseille-Luminy, 1990) | DOI | MR | Zbl

[29] Nguyen, Tung; Scott, Alex; Seymour, Paul A note on the Gyárfás-Sumner conjecture, Graphs Comb., Volume 40 (2024) no. 2, Paper no. 33, 6 pages | Zbl | DOI | MR

[30] Nguyen, Tung; Scott, Alex; Seymour, Paul Induced subgraph density. VI. Bounded VC-dimension, Adv. Math., Volume 482 (2025), Paper no. 110601, 20 pages | DOI | MR | Zbl

[31] Pawlik, Arkadiusz; Kozik, Jakub; Krawczyk, Tomasz; Lasoń, Michał; Micek, Piotr; Trotter, William T.; Walczak, Bartosz Triangle-free intersection graphs of line segments with large chromatic number, J. Comb. Theory, Ser. B, Volume 105 (2014), pp. 6-10 | DOI | MR | Zbl

[32] Rok, Alexandre; Walczak, Bartosz Outerstring graphs are $χ$ -bounded, SIAM J. Discrete Math., Volume 33 (2019) no. 4, pp. 2181-2199 | MR | Zbl | DOI

[33] Scott, Alex Induced trees in graphs of large chromatic number, J. Graph Theory, Volume 24 (1997) no. 4, pp. 297-311 | DOI | MR

[34] Scott, Alex; Seymour, Paul Induced subgraphs of graphs with large chromatic number. XIII. New brooms, Eur. J. Comb., Volume 84 (2020), Paper no. 103024, 21 pages | DOI | MR

[35] Scott, Alex; Seymour, Paul A survey of $χ$ -boundedness, J. Graph Theory, Volume 95 (2020) no. 3, pp. 473-504 | DOI | MR

[36] Scott, Alex; Seymour, Paul; Spirkl, Sophie Polynomial bounds for chromatic number II: Excluding a star-forest, J. Graph Theory, Volume 101 (2022) no. 2, pp. 318-322 | DOI | MR

[37] Scott, Alex; Seymour, Paul; Spirkl, Sophie Polynomial bounds for chromatic number. III. Excluding a double star, J. Graph Theory, Volume 101 (2022) no. 2, pp. 323-340 | DOI | MR

[38] Scott, Alex; Seymour, Paul; Spirkl, Sophie Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree, J. Graph Theory, Volume 102 (2023) no. 3, pp. 458-471 | DOI | MR

[39] Scott, Alex; Seymour, Paul; Spirkl, Sophie Polynomial bounds for chromatic number. IV: A near-polynomial bound for excluding the five-vertex path, Combinatorica, Volume 43 (2023) no. 5, pp. 845-852 | DOI | MR

[40] Suk, Andrew; Tomon, István Hasse diagrams with large chromatic number, Bull. Lond. Math. Soc., Volume 53 (2021) no. 3, pp. 747-758 | DOI | MR

[41] Sumner, David P. Subtrees of a graph and the chromatic number, The theory and applications of graphs, 4th int. Conf., Kalamazoo/ Mich, John Wiley & Sons, 1981, pp. 557-576 | Zbl

Cited by Sources: