The Alon-Tarsi number of subgraphs of a planar graph
classification
🧮 math.CO
keywords
graphplanaralon-tarsichoosablecontainsforesthencenumber
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.