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.


Full Text: PDF