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

D e l t a (H) l e 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.

This page was built for publication: The Alon-Tarsi number of subgraphs of a planar graph