Disproof of the list Hadwiger conjecture

MaRDI QIDQ665753zbMATH OpenFDO

Authors János Barát, Gwenaël Joret, David R. Wood

Publication date 6 March 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.2272, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p232.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

choosable \(K_t\)-minor-free graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Abstract: The List Hadwiger Conjecture asserts that every $K_t$-minor-free graph is $t$-choosable. We disprove this conjecture by constructing a $K_{3t+2}$-minor-free graph that is not $4t$-choosable for every integer $tgeq1$.

Recommendations

• Disproof of the group coloring version of the Hadwiger conjecture
• Disproof of a conjecture by Woodall on the choosability of \(K_{s,t}\)-minor-free graphs
• Improved lower bound for the list chromatic number of graphs with no K_t minor
• Refined List Version of Hadwiger’s Conjecture
• Hadwiger's conjecture

Cited in

(14)

• Connectivity and choosability of graphs with no \(K_t\) minor
• Bipartite graphs with no \(K_6\) minor
• Local Hadwiger's conjecture
• Disproving the Single Level Conjecture
• Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor
• Disproof of the group coloring version of the Hadwiger conjecture
• Thomassen's choosability argument revisited
• Improved lower bound for the list chromatic number of graphs with no K_t minor
• Disproof of a conjecture by Woodall on the choosability of \(K_{s,t}\)-minor-free graphs
• On the choosability of \(H\)-minor-free graphs
• Hadwiger's conjecture
• Maximum 4-degenerate subgraph of a planar graph
• Disproof of a conjecture on list coloring
• Refined List Version of Hadwiger’s Conjecture

This page was built for publication: Disproof of the list Hadwiger conjecture

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