Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911789332037632 |
|---|---|
| author | Delcourt, Michelle Postle, Luke |
| author_facet | Delcourt, Michelle Postle, Luke |
| contents | 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)^β)$-colorable for every $β> 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 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{χ(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$.
One key to proving the main theorem is a new standalone result that every $K_t$-minor-free graph of average degree $d=Ω(t)$ has a subgraph on $O(t \log^3 t)$ vertices with average degree $Ω(d)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_01633 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs Delcourt, Michelle Postle, Luke Combinatorics Discrete Mathematics 05C15, 05C83 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)^β)$-colorable for every $β> 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 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{χ(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$. One key to proving the main theorem is a new standalone result that every $K_t$-minor-free graph of average degree $d=Ω(t)$ has a subgraph on $O(t \log^3 t)$ vertices with average degree $Ω(d)$. |
| title | Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs |
| topic | Combinatorics Discrete Mathematics 05C15, 05C83 |
| url | https://arxiv.org/abs/2108.01633 |