Defective Choosability of Graphs without Small Minors

  • Rupert G. Wood
  • Douglas R. Woodall

Abstract

For each proper subgraph $H$ of $K_5$, we determine all pairs $(k,d)$ such that every $H$-minor-free graph is $(k,d)^*$-choosable or $(k,d)^-$-choosable. The main structural lemma is that the only 3-connected $(K_5-e)$-minor-free graphs are wheels, the triangular prism, and $K_{3,3}$; this is used to prove that every $(K_5-e)$-minor-free graph is 4-choosable and $(3,1)$-choosable.

Published
2009-07-31
Article Number
R92