The Alon-Tarsi number of Halin graphs

Suppose that $G$ has degeneracy $k$ and $\sigma$ is a vertex ordering which witnesses this. By orienting each edge toward its endpoint that appears earlier in the vertex ordering, we can get an acyclic orientation with maximum outdegree $k$. By Lemma 2.1, $AT(G)\leq k+1.$ ∎

By Lemma 3.2, we know that $AT(H)\leq 4$. $H$ has chromatic number 4, so $AT(H)\geq 4$. Hence $AT(H)=4$.

∎

Assume $H=T\cup C_{n}$, $n$ is even. We know that $AT(H)\geq 3$ since $\chi(H)=3$. It remains to show that $AT(H)\leq 3$. Consider the following two cases.

Case 1. $H$ is a wheel with even outer vertices.

Since $H$ is a wheel, $H$ contains exactly one interior vertex $u$, $d(u)=n$, and $d(v_{i})=3$ for $i=1,2,\ldots,n$. Let $D$ be an orientation of $H$ in which the edges of $H$ are oriented in such a way by orientating the outer cycle $C_{n}$ in clockwise and orientating edge $v_{i}u$ as $(v_{i},u),i=1,2,\ldots,n$ [See Figure 1]. $D$ has no odd directed cycle, so $D$ has no odd Eulerian subgraph and hence $D$ is an $AT$-orientation with maximum outdegree 2. Therefore $AT(H)\leq 3$.

Case 2. $H$ is not a wheel with even outer vertices.

Similarly, orient $C_{n}$ in clockwise. For $T$, let $X$ be the set of all the inner vertices that are adjacent to $V(C_{n})$. All the arcs between $V(C_{n})$ and $X$ are oriented from $V(C_{n})$ to $X$. The unoriented edges of $T$ induce a subgraph, denoted by $T_{1}$. It is easy to see that $T_{1}$ has at least two leaves. Let $L_{1}$ and $X_{1}$ be the set of all the leaves of $T_{1}$ and all the vertices of $T_{1}$ that are adjacent to the leaves, respectively. All the arcs between $L_{1}$ and $X_{1}$ are oriented from $L_{1}$ to $X_{1}$. The unoriented edges of $T_{1}$ induce a subgraph, denoted by $T_{2}$. Let $L_{2}$ and $X_{2}$ be the set of all the leaves of $T_{2}$ and all the vertices of $T_{2}$ that are adjacent to the leaves, respectively. All the arcs between $L_{2}$ and $X_{2}$ are oriented from $L_{2}$ to $X_{2}$.

Repeat this process until all edges of $H$ are oriented or only one edge left unoriented, then the edge is oriented arbitrarily. Obviously $D$ has no odd directed cycle, so $D$ has no odd Eulerian subdigraph [See Figure 2]. It is easy to see that the followings hold: (1) $D$ is an $AT$-orientation, (2) $d^{+}_{D}(v)\leq 1$ for each inner vertex $v$, (3) $d^{+}_{D}(v)=2$ for each outer vertex $v$. Hence $AT(H)\leq 3$.
∎

Suppose that $H=T\cup C_{n}$, where $n$ is odd. $H$ has chromatic number 3, so we know that $AT(H)\geq 3$. It remains to show that $AT(H)\leq 3$. Similar to above lemma, we consider two cases.

Case 1. $H$ has a special inner vertex $u$ which is adjacent to an odd number of vertices of $C_{n}$.

Let $v_{1},v_{2},\ldots,v_{k}$ be the neighbors of $u$ on $C_{n}$ and $k$ is odd. Then $\{u,v_{1},v_{2},\ldots,v_{k}\}$ induces a fan, denoted by $G_{1}$. Assume $G_{2}=H-V(G_{1})$. The subgraph $G_{1}$ has an orientation $D_{1}$ as the following way: orient the edge $v_{i}v_{i+1}$ as $(v_{i},v_{i+1})$, for $1\leq i\leq k-1$, the edge $uv_{1}$ as $(u,v_{1})$, and the edge $v_{j}u$ as $(v_{j},u)$ for $j=2,3,\cdots k$. Observe that $uv_{1}v_{2}\ldots v_{i}u$ is an odd directed cycle when $i$ is even, and $uv_{1}v_{2}\ldots v_{i}u$ is an even directed cycle when $i$ is odd, for $2\leq i\leq k$. Hence $D_{1}$ contains $k-1$ directed cycles. Specifically $D_{1}$ contains $\frac{k-1}{2}$ odd directed cycles and $\frac{k-1}{2}$ even directed cycles. It is easy to see that the arc $(u,v_{1})$ is contained in all directed cycles. Since Eulerian subdigraph is the arc disjoint union of directed cycles and empty subdigraph is an even Eulerian subdigraph, $D_{1}$ has $\frac{k-1}{2}$ odd Eulerian subdigraphs and $\frac{k+1}{2}$ even Eulerian subdigraphs. diff$(D_{1})=|\mathcal{E}_{e}(D_{1})|-|\mathcal{E}_{o}(D_{1})|=1\neq 0$. Therefore $D_{1}$ is an $AT$-orientation of $G_{1}$.

Denote $X=\{v_{k+1},v_{k+2},\ldots,v_{n}\}$, and let $X_{1}$ be the set of all the vertices in $V(G_{2})-X$ that are adjacent to $X$. $G_{2}$ has an orientation $D_{2}$ that for each $k+1\leq i\leq n-1$, orient edge $v_{i}v_{i+1}$ as $(v_{i},v_{i+1})$. All the arcs between $X$ and $X_{1}$ are oriented from $X$ to $X_{1}$. The unoriented edges of $G_{2}$ induce a subgraph, denoted by $T_{1}$. Let $L_{1}$ and $X_{2}$ be the set of all the leaves of $T_{1}$ and all the vertices of $T_{1}$ that are adjacent to the leaves, respectively. All the arcs between $L_{1}$ and $X_{2}$ are oriented from $L_{1}$ to $X_{2}$. The unoriented edges of $T_{1}$ induce a subgraph, denoted by $T_{2}$. Let $L_{2}$ and $X_{3}$ be the set of all the leaves of $T_{2}$ and all the vertices of $T_{2}$ that are adjacent to the leaves, respectively. All the arcs between $L_{2}$ and $X_{3}$ are oriented from $L_{2}$ to $X_{3}$. Repeat this process until all edges of $G_{2}$ are oriented or only one edge left unoriented, then the edge is oriented arbitrarily. It is obvious that $D_{2}$ is an acyclic orientation, hence diff$(D_{2})=|\mathcal{E}_{e}(D_{2})|-|\mathcal{E}_{o}(D_{2})|\neq 0$, $D_{2}$ is an $AT$-orientation of $G_{2}$.

Let $v$ be the unique inner vertex which is adjacent to $u$, $u\in V(G_{1})$ and $v\in V(G_{2})$. Let $D$ be obtained from $D_{1}\cup D_{2}$ by adding arcs $(u,v)$, $(v_{1},v_{n})$ and $(v_{k},v_{k+1})$. Such that all the arcs between $G_{1}$ and $G_{2}$ are oriented from $G_{1}$ to $G_{2}$ [See Figure 3]. By Lemma 3.5, $D$ is an $AT$-orientation. It is easy to see that $d^{+}_{D}(v)\leq 2$ for every $v\in V(G)$. Hence $AT(H)\leq 3$.

Case 2. All special inner vertices of $H$ are adjacent to an even number of vertices of $C_{n}$.

Let $u$ be a special inner vertex, $v_{1},v_{2},\ldots,v_{k}$ be the neighbors of $u$ on $C_{n}$. $\{u,v_{1},v_{2},\ldots,v_{k}\}$ induces a fan, denoted by $G_{1}$. Let $G_{2}=H-V(G_{1})$. The subgraph $G_{1}$ has an orientation $D_{1}$ as the following way: orient the edge $v_{i-1}v_{i}$ as $(v_{i},v_{i-1})$ for $2\leq i\leq k$, and the edge $v_{j}u$ as $(v_{j},u)$ for $j=1,2,\ldots k$. Observed that $D_{1}$ is an acyclic orientation, so $D_{1}$ is an $AT$-orientation of $G_{1}$.

In the tree $T$, any two vertices are connected by exactly one path, so there is a unique $xv_{n}$-path in $T$ connecting $x$ and $v_{n}$, where $x\in V(G_{2})\setminus v_{n}$. $G_{2}$ has an orientation $D_{2}$ that for $k+2\leq i\leq n$, orient the edge $v_{i-1}v_{i}$ as $(v_{i},v_{i-1})$, and let every $xv_{n}$-path be a directed path from $x$ to $v_{n}$. It is obvious that all the edges of $G_{2}$ are oriented. Denote $w$ is the unique vertex in $T$ which is adjacent to $v_{n}$, the arc $(w,v_{n})$ is contained in all $xv_{n}$-directed paths. In $G_{2}$, all directed circles are made up of $v_{i}v_{n}$-directed path in $T$ and $v_{n}v_{i}$-directed path in $C_{n}$, for $k+1\leq i\leq n-1$. $D_{2}$ has an even number of directed cycles. Empty subdigraph is an even Eulerian subdigraph of $D_{2}$, hence $|\mathcal{E}(D_{2})|$ is odd. diff$(D_{2})=|\mathcal{E}_{e}(D_{2})|-|\mathcal{E}_{o}(D_{2})|\neq 0$, so $D_{2}$ is an $AT$-orientation of $G_{2}$.

Let $v$ be the unique inner vertex which is adjacent to $u$, $u\in V(G_{1})$ and $v\in V(G_{2})$. Let $D$ be obtained from $D_{1}\cup D_{2}$ by adding arcs $(v,u)$, $(v_{n},v_{1})$ and $(v_{k+1},v_{k})$. Obviously all the arcs between $G_{1}$ and $G_{2}$ are oriented from $G_{2}$ to $G_{1}$ [See Figure 4]. In a similar way as case 1, we can get $AT(H)\leq 3$.

∎