arXiv:2611.24974v1 Announce Type: new Abstract: The \emph{Alon-Tarsi number} $AT(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ admits an orientation $D$ with maximum outdegree at most $k-1$ in which the number of even Eulerian subdigraphs differs from the number of odd Eulerian subdigraphs. A 2-connected planar graph $G$ with minimum degree at least 3 is called a \emph{pseudo-Halin graph} if deleting the edges on the boundary of a single face $f_0$ yields a tree. Let $\mathcal{A}$ denote the class of pseudo-Halin graphs in which no two interior vertices are adjacent and every interior vertex has odd degree (equivalently, graphs obtained by iterated Haj\'{o}s sums of wheels with an odd number of exterior vertices). In this paper, we completely determine the chromatic number and the Alon-Tarsi number of all pseudo-Halin graphs. Specifically, by structural induction and the method of $AT$-orientations, we prove that $AT(G)=\chi(G)=4$ if $G\in\mathcal{A}$, and $AT(G)=\chi(G)=3$ otherwise. Consequently, every pseudo-Halin graph is chromatic-AT choosable.
Continue to arXiv Mathematics →You are being forwarded in 6s — stay on this page