The Alon-Tarsi number of subgraphs of a planar graph

Abstract

This paper constructs a planar graph $G_1$ such that for any subgraph $H$ of $G_1$ with maximum degree $\Delta (H)\le 3$, $G_1-E(H)$ is not $3$-choosable, and a planar graph $G_2$ such that for any star forest $F$ in $G_2$, $G_2-E(F)$ contains a copy of $K_4$ and hence $G_2-E(F)$ is not $3$-colourable. On the other hand, we prove that every planar graph $G$ contains a forest $F$ such that the Alon-Tarsi number of $G-E(F)$ is at most $3$, and hence $G-E(F)$ is 3-paintable and 3-choosable.

12 pages, 5 figures

Cited by in corpus (1)

• The Alon-Tarsi number of planar graphs without cycles of lengths $4$ and $l$