betaFeedback

WorksMathematics

The chromatic-AT choosability of Pseudo-Halin graphs

Abstract

The Alon-Tarsi number AT(G)AT(G) of a graph GG is the smallest integer kk such that GG admits an orientation DD with maximum outdegree at most k−1k-1 in which the number of even Eulerian subdigraphs differs from the number of odd Eulerian subdigraphs. A 2-connected planar graph GG with minimum degree at least 3 is called a pseudo-Halin graph if deleting the edges on the boundary of a single face f0f_0 yields a tree. Let A\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ó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 ATAT-orientations, we prove that AT(G)=χ(G)=4AT(G)=χ(G)=4 if G∈AG\in\mathcal{A}, and AT(G)=χ(G)=3AT(G)=χ(G)=3 otherwise. Consequently, every pseudo-Halin graph is chromatic-AT choosable.

Paper details

vlnc:W_jppnycug
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…