pith. sign in

arxiv: 1906.01506 · v1 · pith:HFUQGXSHnew · submitted 2019-06-04 · 🧮 math.CO

The Alon-Tarsi number of subgraphs of a planar graph

classification 🧮 math.CO
keywords graphplanaralon-tarsichoosablecontainsforesthencenumber
0
0 comments X
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.