Reducing linear Hadwiger’s conjecture to coloring small graphs
HTML articles powered by AMS MathViewer
- by Michelle Delcourt and Luke Postle;
- J. Amer. Math. Soc.
- DOI: https://doi.org/10.1090/jams/1047
- Published electronically: July 24, 2024
- HTML | PDF
Abstract:
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt {\log t})$ and hence is $O(t\sqrt {\log t})$-colorable. Recently, Norin, Song and the second author showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta })$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the $O(t\sqrt {\log t})$ bound. The first main result of this paper is that every graph with no $K_t$ minor is $O(t\log \log t)$-colorable.
This is actually a corollary of our main technical result that the chromatic number of a $K_t$-minor-free graph is bounded by $O(t(1+f(G,t)))$ where $f(G,t)$ is the maximum of $\frac {\chi (H)}{a}$ over all $a\ge \frac {t}{\sqrt {\log t}}$ and $K_a$-minor-free subgraphs $H$ of $G$ that are small (i.e. $O(a\log ^4 a)$ vertices). This has a number of interesting corollaries. First as mentioned, using the current best-known bounds on coloring small $K_t$-minor-free graphs, we show that $K_t$-minor-free graphs are $O(t\log \log t)$-colorable. Second, it shows that proving Linear Hadwiger’s Conjecture (that $K_t$-minor-free graphs are $O(t)$-colorable) reduces to proving it for small graphs. Third, we prove that $K_t$-minor-free graphs with clique number at most $\sqrt {\log t}/ (\log \log t)^2$ are $O(t)$-colorable. This implies our final corollary that Linear Hadwiger’s Conjecture holds for $K_r$-free graphs for every fixed $r$; more generally, we show there exists $C\ge 1$ such that for every $r\ge 1$, there exists $t_r$ such that for all $t\ge t_r$, every $K_r$-free $K_t$-minor-free graph is $Ct$-colorable.
One key to proving the main theorem is building the minor in two new ways according to whether the chromatic number ‘separates’ in the graph: sequentially if the graph is the chromatic-inseparable and recursively if the graph is chromatic-separable. The other key is a new standalone result that every $K_t$-minor-free graph of average degree $d=\Omega (t)$ has a subgraph on $O(t \log ^3 t)$ vertices with average degree $\Omega (d)$.
References
- József Balogh and A. V. Kostochka, Large minors in graphs with given independence number, Discrete Math. 311 (2011), no. 20, 2203–2215. MR 2825665, DOI 10.1016/j.disc.2011.07.003
- Béla Bollobás and Andrew Thomason, Highly linked graphs, Combinatorica 16 (1996), no. 3, 313–320. MR 1417341, DOI 10.1007/BF01261316
- Matija Bucić, Jacob Fox, and Benny Sudakov, Clique minors in graphs with a forbidden subgraph, Random Structures Algorithms 60 (2022), no. 3, 327–338. MR 4388699, DOI 10.1002/rsa.21038
- P. Duchet and H. Meyniel, On Hadwiger’s number and the stability number, Graph theory (Cambridge, 1981) North-Holland Math. Stud., vol. 62, North-Holland, Amsterdam-New York, 1982, pp. 71–73. MR 671905
- Zdeněk Dvořák and Ken-ichi Kawarabayashi, Triangle-free graphs of tree-width $t$ are $\lceil (t+3)/2\rceil$-colorable, European J. Combin. 66 (2017), 95–100. MR 3692139, DOI 10.1016/j.ejc.2017.06.016
- Zdeněk Dvořák and Liana Yepremyan, Independence number in triangle-free graphs avoiding a minor, Proc. Amer. Math. Soc., To appear, DOI:10.1090/proc/1606
- W. Fernandez de la Vega, On the maximum density of graphs which have no subcontraction to $K^{s}$, Discrete Math. 46 (1983), no. 1, 109–110. MR 708172, DOI 10.1016/0012-365X(83)90280-7
- Jacob Fox, Complete minors and independence number, SIAM J. Discrete Math. 24 (2010), no. 4, 1313–1321. MR 2735925, DOI 10.1137/090766814
- António Girão and Bhargav Narayanan, Subgraphs of large connectivity and chromatic number, Bull. Lond. Math. Soc. 54 (2022), no. 3, 868–875. MR 4453744, DOI 10.1112/blms.12569
- H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich 88 (1943), 133–142 (German). MR 12237
- Ken-ichi Kawarabayashi, On the connectivity of minimum and minimal counterexamples to Hadwiger’s conjecture, J. Combin. Theory Ser. B 97 (2007), no. 1, 144–150. MR 2278128, DOI 10.1016/j.jctb.2006.04.004
- Ken-ichi Kawarabayashi and Bojan Mohar, Some recent progress and applications in graph minor theory, Graphs Combin. 23 (2007), no. 1, 1–46. MR 2292102, DOI 10.1007/s00373-006-0684-x
- A. V. Kostochka, The minimum Hadwiger number for graphs with a given mean degree of vertices, Metody Diskret. Analiz. 38 (1982), 37–58 (Russian). MR 713722
- A. V. Kostochka, Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica 4 (1984), no. 4, 307–316. MR 779891, DOI 10.1007/BF02579141
- Daniela Kühn and Deryk Osthus, Minors in graphs of large girth, Random Structures Algorithms 22 (2003), no. 2, 213–225. MR 1954611, DOI 10.1002/rsa.10076
- Daniela Kühn and Deryk Osthus, Complete minors in $K_{s,s}$-free graphs, Combinatorica 25 (2005), no. 1, 49–64. MR 2109193, DOI 10.1007/s00493-005-0004-8
- W. Mader, Existenz $n$-fach zusammenhängender Teilgraphen in Graphen genügend grosser Kantendichte, Abh. Math. Sem. Univ. Hamburg 37 (1972), 86–97 (German). MR 306050, DOI 10.1007/BF02993903
- Karl Menger, Zur allgemeinen kurventheorie, Fund. Math. 10 (1927), 96–115.
- Michael Molloy, The list chromatic number of graphs with small clique number, J. Combin. Theory Ser. B 134 (2019), 264–284. MR 3906639, DOI 10.1016/j.jctb.2018.06.007
- Tung H. Nguyen, Highly connected subgraphs with large chromatic number, SIAM J. Discrete Math. 38 (2024), no. 1, 243–260. MR 4686382, DOI 10.1137/22M150040X
- Sergey Norin and Luke Postle, Connectivity and choosability of graphs with no $K_ t$ minor. part 1, J. Combin. Theory Ser. B 158 (2023), no. part 1, 283–300. MR 4513825, DOI 10.1016/j.jctb.2021.02.001
- Sergey Norin, Luke Postle, and Zi-Xia Song, Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor, Adv. Math. 422 (2023), Paper No. 109020, 23. MR 4576840, DOI 10.1016/j.aim.2023.109020
- Bruce Reed and Paul Seymour, Fractional colouring and Hadwiger’s conjecture, J. Combin. Theory Ser. B 74 (1998), no. 2, 147–152. MR 1654153, DOI 10.1006/jctb.1998.1835
- Neil Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B 63 (1995), no. 1, 65–110. MR 1309358, DOI 10.1006/jctb.1995.1006
- Paul Seymour, Hadwiger’s conjecture, Open problems in mathematics, Springer, [Cham], 2016, pp. 417–437. MR 3526944
- Robin Thomas and Paul Wollan, An improved linear edge bound for graph linkages, European J. Combin. 26 (2005), no. 3-4, 309–324. MR 2116174, DOI 10.1016/j.ejc.2004.02.013
- Andrew Thomason, An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc. 95 (1984), no. 2, 261–265. MR 735367, DOI 10.1017/S0305004100061521
- Paul Wollan, Extremal functions for rooted minors, J. Graph Theory 58 (2008), no. 2, 159–178. MR 2407003, DOI 10.1002/jgt.20301
Bibliographic Information
- Michelle Delcourt
- Affiliation: Department of Mathematics, Toronto Metropolitan University, Toronto, Ontario M5B 2K3, Canada
- MR Author ID: 923919
- Email: mdelcourt@torontomu.ca
- Luke Postle
- Affiliation: Combinatorics and Optimization Department, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
- MR Author ID: 898019
- ORCID: 0000-0002-5023-269X
- Email: lpostle@uwaterloo.ca
- Received by editor(s): May 2, 2022
- Received by editor(s) in revised form: July 14, 2023, and May 7, 2024
- Published electronically: July 24, 2024
- Additional Notes: Research of the first author was supported by NSERC under Discovery Grant No. 2019-04269. The work of the second author was partially supported by NSERC under Discovery Grant No. 2019-04304.
- © Copyright 2024 by the authors
- Journal: J. Amer. Math. Soc.
- MSC (2020): Primary 05C15; Secondary 05C83
- DOI: https://doi.org/10.1090/jams/1047
Dedicated: Dedicated to the memory of Robin Thomas