PreprintarXiv licencearXiv
Coloring Small Kt-Minor-Free Graphs
Abstract
Delcourt and Postle proved that every Kt-minor-free graph is O(tloglog t)-colorable and reduced the Linear Hadwiger Conjecture to coloring Kt-minor-free graphs on O(tlog4 t) vertices. In this paper, we use the star contraction technique to improve their bound for small graphs and use their reduction to extend this improvement to all Kt-minor-free graphs. Thus we improve their O(tloglog t) bound to O(t√(loglog t)).
Related
- Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
- Two-coloring cubic graphs with small monochromatic components, but without singletons
- A note on highly connected K2,ℓ -minor free graphs
- On separators in Kt-minor-free graphs
- On the maximum degree and order of Kt-minor-free graphs with positive Lin--Lu--Yau curvature
BibTeX
@misc{lin2026coloring,
title = {{Coloring Small $K_t$-Minor-Free Graphs}},
author = {Xinheng Lin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08713},
eprint = {2609.08713},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08713},
}
RIS
TY - UNPB
TI - Coloring Small K_t-Minor-Free Graphs
AU - Xinheng Lin
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08713
UR - https://arxiv.org/abs/2609.08713
AB - Delcourt and Postle proved that every K_t-minor-free graph is O(tloglog t)-colorable and reduced the Linear Hadwiger Conjecture to coloring K_t-minor-free graphs on O(tlog^4 t) vertices. In this paper, we use the star contraction technique to improve their bound for small graphs and use their reduction to extend this improvement to all K_t-minor-free graphs. Thus we improve their O(tloglog t) bound to O(t√(loglog t)).
ER -