Connectivity and choosability of graphs with no K_t minor

DOI10.1016/J.JCTB.2021.02.001MaRDI QIDQ2099418zbMATH OpenOpenAlexFDO

Authors Serguei Norine, Luke Postle

Publication date 23 November 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.10367

zbMATH Keywords

connectivitygraph minorsHadwiger's conjecturelist coloring

Mathematics Subject Classification ID

Connectivity (05C40) Graph minors (05C83) Combinatorial probability (60C05)

Abstract: In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $tge1$. While Hadwiger's conjecture does not hold for list-coloring, the linear weakening is conjectured to be true. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(tsqrtlogt)$ and thus is $O(tsqrtlogt)$-list-colorable. Recently, the authors and Song proved that every graph with no $K_t$ minor is $$-colorable for every $$. Here, we build on that result to show that every graph with no $K_t$ minor is $$-list-colorable for every $$. Our main new tool is an upper bound on the number of vertices in highly connected $K_t$-minor-free graphs: We prove that for every $$, every $$-connected graph with no $K_t$ minor has $O(t(logt{)}^{7/4})$ vertices.

Recommendations

• Improved lower bound for the list chromatic number of graphs with no K_t minor
• Breaking the degeneracy barrier for coloring graphs with no K_t minor
• List-coloring graphs without \(K_{4,k}\)-minors
• Coloring graphs with forbidden minors
• Disproof of a conjecture by Woodall on the choosability of \(K_{s,t}\)-minor-free graphs

Cites work

• A local epsilon version of Reed's conjecture
• A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor
• A relaxed Hadwiger's conjecture for list colorings
• An extremal function for contractions of graphs
• Breaking the degeneracy barrier for coloring graphs with no K_t minor
• Choice Numbers of Graphs: a Probabilistic Approach
• Disproof of the list Hadwiger conjecture
• Fractional colouring and Hadwiger's conjecture
• Hadwiger's conjecture
• Hadwiger's conjecture is true for almost every graph
• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• Linear connectivity forces large complete bipartite minors
• List colourings of planar graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• On Hadwiger's Number and the Stability Number
• On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Some recent progress and applications in graph minor theory
• Subgraphs of large connectivity and chromatic number
• The extremal function for complete minors

Cited in

(14)

• List-coloring graphs without \(K_{4,k}\)-minors
• Disproof of a conjecture by Woodall on the choosability of \(K_{s,t}\)-minor-free graphs
• Breaking the degeneracy barrier for coloring graphs with no K_t minor
• Improved bound for improper colourings of graphs with no odd clique minor
• Improved lower bound for the list chromatic number of graphs with no K_t minor
• Subgraphs of large connectivity and chromatic number
• Local Hadwiger's conjecture
• Refined List Version of Hadwiger’s Conjecture
• Packing list‐colorings
• On the choosability of \(H\)-minor-free graphs
• Dominating K_t-models
• Refined list version of Hadwiger's conjecture (extended abstract)
• Reducing linear Hadwiger's conjecture to coloring small graphs
• Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's conjecture

This page was built for publication: Connectivity and choosability of graphs with no \(K_t\) minor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2099418)