The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda

Zhiguo Li^∗ , Yujia Gai, Zeling Shao

Department of Mathematics, Hebei University of Technology, China

zhiguolee@hebut.edu.cn, 202221101013@stu.hebut.edu.cn, zelingshao@163.com

The Alon-Tarsi number of a graph G is the smallest k so that there exists an orientation D of G with max outdegree k − 1 satisfying the number of even Eulerian subgraphs different from the number of odd Eulerian subgraphs. This paper is devoted to the study of the Alon-Tarsi number of cupolarotundas and gyroelongated rotunda.

Keywords: Alon-Tarsi number, choice number, chromatic number, Combinatorial Nullstellensatz, planar graph

Mathematics Subject Classification : 05C15

DOI: 10.5614/ejgta.2024.12.2.5

1. Introduction

We only consider simple and finite graphs in this paper. The chromatic number of a graph G, denoted by χ(G), is the least positive integer k such that G has a proper vertex coloring using k colors. List coloring is a well-known variation on vertex coloring. For list coloring, a k-list assignment of a graph G is a mapping L which assigns to each vertex v of G a set L(v) of k permissible colors. An L-coloring of G is a coloring f of G such that f(v) ∈ L(v) for each vertex v. We say G is L-colorable if there exists a proper L-coloring of G. A graph G is k-choosable if G is L-colorable for every k-list assignment L. The choice number of a graph G is the least positive integer k such that G is k-choosable, denoted by ch(G).

A subdigraph H of a directed graph D is called Eulerian if V (H) = V (G) and the indegree d − ^H(v) of every vertex v of H in H is equal to its outdegree d + ^H(v). We do not assume that H

Received: 30 November 2023, Revised: 17 June 2024, Accepted: 23 June 2024.

is connected. H is even if it has an even number of edges, otherwise, it is odd. Let \(\mathcal{E}_e(D)\) and \(\mathcal{E}_o(D)\) denote the family of even and odd Eulerian subgraphs of D, respectively. Let \(diff(D) = |\mathcal{E}_e(D)| - |\mathcal{E}_o(D)|\). We say that D is Alon-Tarsi if \(diff(D) \neq 0\). If an orientation D of G yields an Alon-Tarsi digraph, then we say D is an Alon-Tarsi orientation (AT-orientation, for short) of G [1].

The Alon-Tarsi number of G (AT(G), for short) is the smallest k so that there exists an orientation D of G with max outdegree k-1 satisfying the number of Eulerian subgraphs with even edges different from the number of Eulerian subgraphs with odd edges. It was proposed by Alon and Tarsi [4], subsequently, they used algebraic methods to prove that \(\chi(G) \leq ch(G) \leq AT(G)\). The graph G is called chromatic-choosable if \(\chi(G) = ch(G)\). The graph G is called chromatic-AT choosable if \(\chi(G) = AT(G)\). There are some results concerning the Alon-Tarsi number of planar graphs. Zhu [10] showed that every planar graph G has \(AT(G) \leq 5\). Grytczuk and Zhu proved that every planar graph G has a matching G such that G in [3]. Zhu and Kim also showed that every planar graph G has a forest G such that G in [6]. Zhu and Lu [9] used the discharging method to show that for G is G and G in [6]. Zhu and G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G such that G is a matching G suc

There are also some conclusions for special graphs, Zhu and Balakrishnan [11] proved that bipartite graph G has \(AT(G) = \max_{H \subset G} \lceil \frac{|E(H)|}{|V(H)|} \rceil + 1\), they also showed that bipartite planar graphs G have \(AT(G) \leq 3\). There are some conclusions about the Cartesian product of graphs, Kaul and Mudrock proved that the Cartesian product of any cycle with a path with at least two vertices has the Alon-Tarsi number 3 in [5]. Suppose that G is a complete graph or an odd cycle with \(|V(G)| \geq 3\). Suppose H is a graph on at least two vertices that contains a Hamilton path \(\omega_1, \omega_2, \ldots, \omega_n\), such that \(\omega_i\) has at most k neighbors among \(\omega_1, \omega_2, \ldots, \omega_{i-1}\), Kaul, Mudrock [5] also proved the Cartesian product of G and H has \(AT(G \square H) \leq \Delta(G) + k\). The first author and Shao et al. proved that the Cartesian product of \(C_m\) and \(C_n\) has the Alon-Tarsi number 4 when n and m are both odd and 3 otherwise in [7].

A graph G is a polyhedral graph if G is isomorphic to the 1-skeleton of a three-dimensional convex polyhedron P. According to Steinitz's theorem [2], every polyhedral graph is planar and 3-connected. Rotunda and cupola play important roles in polyhedral graphs. Moreover, they can also extend a variety of polyhedral graphs.

A cupola is formed by joining two parallel polygons, one as the top surface, the other as the bottom of the polygon with twice the number of edges, and its sides are formed by a combination of triangles and quadrangles. An n-gonal cupola \(Q_n\) has 3n vertices, 5n edges. The rotunda is similar to the cupola but instead of alternating quadrangles and triangles, it is composed of alternating pentagons and triangles. An n-gonal rotunda has 4n vertices, 7n edges.

There are some ways cupola and rotunda can be combined. The first cupolarotunda \(R_{Q_n}^I\) is an infinite set of polyhedra, constructed by adjoining an n-gonal cupola to a 2n-gonal rotunda (see Figure 1 (a) for n=3). For \(n\geq 3\), a \(R_{Q_n}^I\) has 5n triangles, n squares, 2n pentagons, an n-gonal and a 4n-gonal as faces. We use |V(G)| and |E(G)| for the number of vertices and edges in graph

G, it is easy to see \(|V(R_{Q_n}^I)|=9n\) and \(|E(R_{Q_n}^I)|=17n\). The second cupolarotunda \(R_{Q_n}^{II}\) is an infinite set of polyhedra, constructed by adjoining an n-gonal rotunda to a 2n-gonal cupola (see Figure 1 (b) for n=3). For \(n\geq 3\), a \(R_{Q_n}^{II}\) has 4n triangles, 2n squares, n pentagons, an n-gonal and a 4n-gonal as faces, and \(|V(R_{Q_n}^{II})|=8n\), \(|E(R_{Q_n}^{II})|=15n\).

Figure 1. (a) A cupolarotunda \(R_{Q_3}^I\) and (b) a cupolarotunda \(R_{Q_3}^{II}\).

Antiprism also plays an important role in polyhedral graphs. The gyroelongated rotunda \(G_{R_n}\) is an infinite set of polyhedra, constructed by adjoining an n-gonal rotunda to a 2n-gonal antiprism (see Figure 2 for n=3). For \(n\geq 3\), a gyroelonged rotunda has 6n triangles, n pentagons, an n-gonal and a 2n-gonal as faces, and \(|V(G_{R_n})|=6n\), \(|E(G_{R_n})|=13n\).

Figure 2. Gyroelongated rotunda \(G_{R_3}\).

Lemma 1.1. Given an orientation D of graph G, if D has no odd directed cycle, then D is an AT-orientation of G.

Our goal is to compute the exact value of the Alon-Tarsi number of cupolarotundas \(R_{Q_n}^I\), \(R_{Q_n}^{II}\), and gyroelongated rotunda \(G_{R_n}\). The main results are the following theorems:

Theorem 1. For cupolar ot und as \(R_{Q_n}^I\) and \(R_{Q_n}^{II}\), we have

\[AT(R_{Q_n}^I) = AT(R_{Q_n}^{II}) = 3.\]

Theorem 2. For a gyroelongated rotunda \(G_{R_n}\), we have

\[AT(G_{R_n}) = 4.\]

2. The Proof of the Theorem 1

Assume \(V(R_{Q_n}^I)=\{u_1,u_2,\ldots,u_n,v_1,v_2,\ldots,v_{2n},v_1',v_2',\ldots,v_{2n}',w_1,w_2,\ldots,w_{4n}\}\). The top cycle \(u_1u_2\cdots u_nu_1\) is called \(C_1\), the middle cycle \(v_1v_2\cdots v_{2n}v_1\) is called \(C_2\) and the bottom cycle \(w_1w_2\cdots w_{4n}w_1\) is called \(C_3\); the vertices \(v_1',v_2',\ldots,v_{2n}'\) are points located between \(C_2\) and \(C_3\). For \(i=1,\ldots,n\), the vertices \(u_iv_{2i}v_{2i-1}\) form a triangle and \(u_iu_{i+1}v_{2i+1}v_{2i}\) form a quadrangle. For \(j=1,\ldots,2n\), the vertices \(v_j'v_jv_{j+1}\) form a triangle, \(v_j'w_{2j}w_{2j-1}\) form a triangle and \(v_i'v_{j+1}v_{j+1}'w_{2j+1}w_{2j}\) form a pentagon (see Figure 3).

The proof of Theorem 1 will be completed by the following lemmas.

Lemma 2.1. For a cupolarotunda \(R_{Q_n}^I\),

\[\chi(R_{Q_n}^I) = 3.\]

Proof. It is easily seen that \(R_{Q_n}^I\) contains a triangle as its subgraph, hence \(\chi(R_{Q_n}^I) \geq 3\). It remains to show that \(\chi(R_{Q_n}^I) \leq 3\). It suffices to show that \(\phi\colon V(R_{Q_n}^I) \to \{0,1,2\}\) is a proper 3-coloring of \(R_{Q_n}^I\).

Case 1. n is even.

For the vertices in \(C_1\), let \(\phi(u_1) = 2\). For i = 2, ..., n, let \(\phi(u_i) = 1\) when i is an odd number and \(\phi(u_i) = 0\) when i is an even number.

For the vertices in \(C_2\), for \(j=1,\ldots,2n\), let \(\phi(v_j)=0\) or 1 when j is an even number. Therefore, for \(i=2,\ldots,n\), if \(\phi(u_i)=1\), then \(\phi(v_{2i})=0, \phi(v_{2i-1})=2\); if \(\phi(u_i)=0\), then \(\phi(v_{2i})=1, \phi(v_{2i-1})=2\). Since n is even, we have \(\phi(u_n)=0, \phi(v_{2n})=1\); the neighbours of \(v_1\) are \(u_1,v_{2n}\), and \(u_1v_1v_2\) form a triangle, it is easy to know that \(\phi(v_1)=0, \phi(v_2)=1\).

Then \(\phi(v_j')\) can be determined in a unique way.

For the vertices in \(C_3\), for \(j=1,\ldots,2n\), the neighbours of \(v_j'\) are \(v_j,v_{j+1},w_{2j},w_{2j-1}\). Let \(\phi(v_j)=\phi(w_{2j}),\ \phi(v_{j+1})=\phi(w_{2j-1})\) when j is an even number and let \(\phi(v_j)=\phi(w_{2j-1}),\ \phi(v_{j+1})=\phi(w_{2j})\) when j is an odd number. We can know that \(\phi\) is a proper coloring of \(R_{Q_n}^I\).

Case 2. n is odd.

This is similar to what happens in case 1. Since n is odd, we have \(\phi(u_n)=1, \phi(v_{2n})=0\); the neighbours of \(v_1\) are \(u_1, v_{2n}\), and \(u_1v_1v_2\) form a triangle, it is easy to know that \(\phi(v_1)=1\), \(\phi(v_2)=0\). The other points are colored in the same way in case 1, we can know that \(\phi\) is a proper coloring of \(R_{Q_n}^I\). (See Figure 3 (a) for n=4, (b) for n=5)

Hence \(\chi(\hat{R}_{Q_n}^I) \leq 3\).

Figure 3. (a) A proper 3-coloring of \(R_{Q_4}^I\) and (b) for \(R_{Q_5}^I\).

Lemma 2.2. For a cupolarotunda \(R_{O_n}^I\),

\[AT(R_{O_n}^I) = 3.\]

Proof. By Lemma 2.1, \(AT(R_{Q_n}^I) \ge \chi(R_{Q_n}^I) = 3\). What is left is to show that \(AT(R_{Q_n}^I) \le 3\). We denote L(n) as the set of edges belonging to quadrangles connecting \(C_1\) and \(C_2\).

We give \(R_{Q_n}^I\) an orientation D. The rules of orientation D are as follows:

R1: For the cycles \(C_2\), \(C_3\) are clockwise. For the cycle \(C_1\), \(u_1u_2\) is oriented from \(u_2\) to \(u_1\), \(u_iu_{i+1}\) is oriented from \(u_i\) to \(u_{i+1}\) \((i=2,\ldots,n)\).

R2: The edges belonging to L(n) are oriented from \(C_2\) to \(C_1\).

R3: For \(j=1,2,\ldots,2n\), let \(v_jv_j',v_{j+1}v_j'\) are oriented from \(v_j'\) to \(v_j,v_{j+1}\) and let the edges \(v_j'w_{2j},v_j'w_{2j-1}\) are oriented from \(w_{2j},w_{2j-1}\) to \(v_j'\).

Since the orientation D has no odd directed cycle, by Lemma 1.1, D is an AT-orientation, and it is easy to see that every vertex \(x \in V(R_{Q_n}^I)\) has outdegree at most 2, so \(AT(R_{Q_n}^I) \leq 3\) (see Figure 4 (a) for n=4,(b) for n=5).

Assume \(V(R_{Q_n}^{II})=\{v_1,v_2,\ldots,v_n,v_1',v_2',\ldots,v_n',u_1,u_2,\ldots,u_{2n},w_1,w_2,\ldots,w_{4n}\}\). The top cycle \(v_1v_2\ldots v_nv_1\) is called \(C_1\), the middle cycle \(u_1u_2\ldots u_{2n}u_1\) is called \(C_2\) and the bottom cycle \(w_1w_2\ldots w_{4n}w_1\) is called \(C_3\); the vertices \(v_1',v_2',\ldots,v_n'\) are points located between \(C_1\) and \(C_2\). For \(i=1,\ldots,n\), the vertices \(v_i'v_iv_{i+1}\) form a triangle, \(v_i'u_{2i}u_{2i-1}\) form a triangle and \(v_i'v_{i+1}v_{i+1}'u_{2i+1}u_{2i}\) form a pentagon. For \(j=1,\ldots,2n,u_jw_{2j}w_{2j-1}\) form a triangle and \(u_ju_{j+1}w_{2j+1}\) \(w_{2j}\) form a quadrangle (see Figure 5).

Lemma 2.3. For a cupolarotunda \(R_{Q_n}^{II}\),

\[\chi(R_{Q_n}^{II}) = 3.\]

Figure 4. (a) An orientation of \(R_{Q_4}^I\) and (b) for \(R_{Q_5}^I\).

Proof. It is easily seen that \(R_{Q_n}^{II}\) contains a triangle as its subgraph, hence \(\chi(R_{Q_n}^{II}) \geq 3\). It remains to show that \(\chi(R_{Q_n}^{II}) \leq 3\). It suffices to show that \(\phi \colon V(R_{Q_n}^{II}) \to \{0,1,2\}\) is a proper 3-coloring of \(R_{Q_n}^{II}\).

Case 1. \(n \equiv 0 \pmod{3}\).

For the vertices in \(C_3\). For k = 1, 2, ..., 4n, let \(\phi(w_k) = 0\) if \(k \equiv 1 \pmod{3}\); let \(\phi(w_k) = 1\) if \(k \equiv 2 \pmod{3}\) and let \(\phi(w_k) = 2\) if \(k \equiv 0 \pmod{3}\). The coloring of the remaining vertices can be uniquely determined.

For the vertices in \(C_2\). For \(j=1,2,\ldots,2n\), since \(u_jw_{2j}w_{2j-1}\) form a triangle, we have \(\phi(u_j)=2\) if \(j\equiv 1\ (\text{mod }3)\); \(\phi(u_j)=1\) if \(j\equiv 2\ (\text{mod }3)\) and \(\phi(u_j)=0\) if \(j\equiv 0\ (\text{mod }3)\).

For i = 1, 2, ..., n, since \(v_i'u_{2i}u_{2i-1}\) form a triangle, we have \(\phi(v_i') = 0\) if \(i \equiv 1 \pmod 3\); \(\phi(v_i') = 1\) if \(i \equiv 2 \pmod 3\) and \(\phi(v_i') = 2\) if \(i \equiv 0 \pmod 3\).

For the vertices in \(C_1\). Since \(v_i\) is adjacent \(v_i', v_{i-1}',\) hence \(\phi(v_i) = 1\) if \(i \equiv 1 \pmod 3\); \(\phi(v_i) = 2\) if \(i \equiv 2 \pmod 3\) and \(\phi(v_i) = 0\) if \(i \equiv 0 \pmod 3\) (see Figure 5 (a) for n = 3).

Case 2. \(n \equiv 1 \pmod{3}\).

For the vertices in \(C_1\), let \(\phi(v_n)=1\). For \(i=1,2,\ldots,n-1\), let \(\phi(v_i)=0\) if \(i\equiv 1\pmod 3\); \(\phi(v_i)=1\) if \(i\equiv 2\pmod 3\) and let \(\phi(v_i)=2\) if \(i\equiv 0\pmod 3\).

Let \(\phi(v'_{n-1}) = 0\), \(\phi(v'_n) = 2\). For i = 1, 2, ..., n-2, let \(\phi(v'_i) = 2\) if \(i \equiv 1 \pmod{3}\); \(\phi(v'_i) = 0\) if \(i \equiv 2 \pmod{3}\) and let \(\phi(v'_i) = 1\) if \(i \equiv 0 \pmod{3}\).

For the vertices in \(C_2\), note that \(v_i'\) is adjacent \(v_i, v_{i+1}, u_{2i}, u_{2i-1}\). When n is an even number, for \(i=1,2,\ldots,n\), let \(\phi(v_i)=\phi(u_{2i}),\,\phi(v_{i+1})=\phi(u_{2i-1})\) when i is an even number and \(\phi(v_{i+1})=\phi(u_{2i}),\,\phi(v_i)=\phi(u_{2i-1})\) when i is an odd number. When n is an odd number, let \(\phi(u_{2n})=1,\phi(u_{2n-1})=0\) and for \(i=1,2,\ldots,n-1\), let \(\phi(v_i)=\phi(u_{2i}),\,\phi(v_{i+1})=\phi(u_{2i-1})\) when i is an even number and \(\phi(v_{i+1})=\phi(u_{2i}),\,\phi(v_i)=\phi(u_{2i-1})\) when i is an odd number.

For the vertices in \(C_3\), we know that \(u_{2i}\) is adjacent \(w_{4i}\), \(w_{4i-1}\) and \(u_{2i-1}\) is adjacent \(w_{4i-2}\), \(w_{4i-3}\).

When n is an odd number, let \(\phi(w_{4n-7})=2\), \(\phi(w_{4n-6})=\phi(w_{4n-4})=0\), \(\phi(w_{4n-5})=1\). For \(i=1,2,\ldots,n-2,n\), let \(\phi(v_i')=\phi(w_{4i-1})=\phi(w_{4i-3})\) when i is an even number and \(\phi(v_i')=\phi(w_{4i})=\phi(w_{4i-2})\) when i is an odd number. When n is an even number, for \(i=1,2,\ldots,n\), let \(\phi(v_i')=\phi(w_{4i-1})=\phi(w_{4i-3})\) when i is an even number and \(\phi(v_i')=\phi(w_{4i})=\phi(w_{4i-2})\) when i is an odd number (see Figure 5 (b) for n=4, Figure 7 (a) for n=7).

Figure 5. (a) A proper 3-coloring of \(R_{Q_3}^{II}\) and (b) for \(R_{Q_4}^{II}\).

Case 3. \(n \equiv 2 \pmod{3}\).

This is similar to what happens in case 2. For the vertices in \(C_1\), let \(\phi(v_{n-1}) = 1\), \(\phi(v_n) = 2\). The other points are colored in the same way as \(C_1\) in case 2, it is easy to know that \(\phi(v_i')\) is colored in a unique way (i = 1, ..., n).

For the vertices in \(C_2\), let \(\phi(u_{2n}) = 2\), \(\phi(u_{2n-1}) = 0\). The other points are colored in the same way as \(C_2\) in case 2.

For the vertices in \(C_3\). When n is an even number, let \(\phi(w_{4n-9}) = 1\), \(\phi(w_{4n-8}) = \phi(w_{4n-10}) = 0\), \(\phi(w_{4n-11}) = 2\) and for \(i = 1, 2, \ldots, n-3, n-1, n\), \(\phi(w_{4i})\), \(\phi(w_{4i-1})\), \(\phi(w_{4i-2})\), \(\phi(w_{4i-3})\) are similar to \(C_3\) in case 2. When n is an odd number, let \(\phi(w_{4n}) = 0\), \(\phi(w_{4n-1}) = \phi(w_{4n-3}) = 1\), \(\phi(w_{4n-2}) = 2\) and let \(\phi(w_{4n-4}) = \phi(w_{4n-6}) = 0\), \(\phi(w_{4n-5}) = 2\), \(\phi(w_{4n-7}) = 1\) and for \(i = 1, 2, \ldots, n-2\), \(\phi(w_{4i})\), \(\phi(w_{4i-1})\), \(\phi(w_{4i-2})\), \(\phi(w_{4i-3})\) are similar to \(C_3\) in case 2 (see Figure 6 (a) for n = 5, Figure 7 (b) for n = 8).

Lemma 2.4. For a cupolarotunda \(R_{Q_n}^{II}\),

\[AT(R_{O_n}^{II}) = 3.\]

Proof. By Lemma 2.3, \(AT(R_{Q_n}^{II}) \geq \chi(R_{Q_n}^{II}) = 3\). What is left is to show that \(AT(R_{Q_n}^{II}) \leq 3\), the orientation method is similar to \(R_{Q_n}^{I}\). Since the orientation D has no odd directed cycle, by Lemma 1.1, D is an AT-orientation and it is easy to see that every vertex \(x \in V(R_{Q_n}^{II})\) has outdegree at most 2, so \(AT(R_{Q_n}^{II}) \leq 3\) (see Figure 6 (b) for n=3).

Figure 6. (a) A proper 3-coloring of RII Q⁵ and (b) an orientation of RII Q³ .

Figure 7. (a) Local points coloring of RII Q⁷ and (b) for RII Q⁸ .

Corollary 2.1. Cupolarotundas \(R_{Q_n}^I\) and \(R_{Q_n}^{II}\) are chromatic-AT choosable, where \(n \geq 3\).

3. The Proof of the Theorem 2

Assume \(V(G_{R_n})=\{u_1,u_2,\ldots,u_n,u_1',u_2',\ldots,u_n',v_1,v_2,\ldots,v_{2n},v_1',v_2',\ldots,v_{2n}'\}\). The top cycle \(u_1u_2\cdots u_nu_1\) is called \(C_1\), the middle cycle \(v_1v_2\cdots v_{2n}v_1\) is called \(C_2\) and the bottom cycle \(v_1'v_2'\cdots v_{2n}'v_1'\) is called \(C_3\); the vertices \(u_1',u_2',\ldots,u_{2n}'\) are points located between \(C_1\) and \(C_2\). For \(i=1,\ldots,n\), the vertices \(u_i'u_iu_{i+1}\) form a triangle, \(u_i'v_{2i}v_{2i-1}\) form a triangle and \(u_i'u_{i+1}u_{i+1}'v_{2i+1}v_{2i}\) form a pentagon. For \(j=1,\ldots,2n,v_jv_{j+1}v_{j+1}'\) form a triangle and \(v_jv_j'v_{j+1}'\) form a triangle (see Figure 8).

The proof of Theorem 2 will be completed by the following lemmas.

Lemma 3.1. For a gyroelongated rotunda \(G_{R_n}\),

\[\chi(G_{R_n}) = \begin{cases} 3, & \text{if } n \equiv 0 \pmod{3}; \\ 4, & \text{otherwise.} \end{cases}\]

Proof. It is easy to see that \(G_{R_n}\) contains a triangle as its subgraph, hence \(\chi(G_{R_n}) \geq 3\). By the Four-Color Theorem, \(\chi(G_{R_n}) \leq 4\).

Let \(\phi: V(G_{R_n}) \to \{0,1,2\}\). Without loss of generality, let \(\phi(v_1') = 0\) and \(\phi(v_2') = 1\), it is a simple matter to obtain the colors of \(v_1, \ldots, v_{2n}, v_3', \ldots, v_{2n}'\) in a unique way. For \(q = 0, 1, \ldots, \lfloor \frac{2n}{3} \rfloor\), we have \(\phi(v_{3q+1}') = 0\), \(\phi(v_{3q+2}') = 1\), \(\phi(v_{3q+3}') = 2\) and \(\phi(v_{3q+1}) = 2\), \(\phi(v_{3q+2}) = 0\), \(\phi(v_{3q+3}) = 1\).

Case 1. \(n \equiv 1 \pmod{3}\).

When \(n \equiv 1 \pmod{3}\), \(2n \equiv 2 \pmod{3}\). By the above rule, we have \(\phi(v'_{2n}) = 1, \phi(v_{2n}) = 0\). It is easy to see that \(v_{2n}\) is the neighbor of \(v'_1\), but \(\phi(v'_1) = 0\), that a contradiction. Hence it is not 3-colorable (see Figure 8 (a) for n = 4).

Case 2. \(n \equiv 2 \pmod{3}\).

When \(n \equiv 2 \pmod{3}\), \(2n \equiv 1 \pmod{3}\). By the above rule, we have \(\phi(v'_{2n}) = 0\), \(\phi(v_{2n}) = 2\). Note that \(v'_{2n}\) is adjacent to \(v'_1\), but \(\phi(v'_1) = 0\), that a contradiction. Hence it is not 3-colorable (see Figure 8 (b) for n = 5).

Case 3. \(n \equiv 0 \pmod{3}\).

When \(n \equiv 0 \pmod{3}\), \(2n \equiv 0 \pmod{3}\), we can give a 3-coloring as follows:

For \(q = 0, 1, \ldots, \lfloor \frac{2n}{3} \rfloor\), let \(\phi(v'_{3q+1}) = 0\), \(\phi(v'_{3q+2}) = 1\), \(\phi(v'_{3q+3}) = 2\) and let \(\phi(v_{3q+1}) = 2\), \(\phi(v_{3q+2}) = 0\), \(\phi(v_{3q+3}) = 1\).

For \(p=0,1,\ldots,\lfloor\frac{n}{3}\rfloor\), let \(\phi(u'_{3p+1})=1\), \(\phi(u'_{3p+2})=0\), \(\phi(u'_{3p+3})=2\) and let \(\phi(u_{3p+1})=0\), \(\phi(u_{3p+2})=2\), \(\phi(u_{3p+3})=1\). It is a proper 3-coloring (see Figure 9 for n=3).

Lemma 3.2. For a gyroelongated rotunda \(G_{R_n}\),

\[AT(G_{R_n}) = 4.\]

Proof. The \(G_{R_n}\) has 6n vertices and 13n edges. Since \(\sum_{x \in V(D)} d_D^+(x) = |A(D)|\), by the Pigeonhole Principle, there exists some vertices have outdegree at least 3 for any orientation D of \(G_{R_n}\). Hence \(AT(G_{R_n}) \geq 4\). What is left is to show that \(AT(G_{R_n}) \leq 4\).

Figure 8. (a) An improper 3-coloring of GR⁴ and (b) for GR⁵ .

Figure 9. A proper 3-colouring of G^R3 .

We give \(G_{R_n}\) an orientation D. The rules of orientation D are given as following:

R1: For the cycles \(C_2\), \(C_3\) are clockwise. For the cycle \(C_1\), \(u_1u_2\) is oriented from \(u_2\) to \(u_1\), \(u_iu_{i+1}\) is oriented from \(u_i\) to \(u_{i+1}\) \((i=2,\ldots,n)\).

R2: For \(i=1,2,\ldots,n\), let the edges \(u_i'u_i,\ u_i'u_{i+1}\) are oriented from \(u_i'\) to \(u_i,u_{i+1}\) and let \(u_i'v_{2i},u_i'v_{2i-1}\) are oriented from \(v_{2i},v_{2i-1}\) to \(u_i'\).

R3: For j = 1, 2, ..., 2n, let the edges \(v'_j v_j\) is oriented from \(v'_j\) to \(v_j\) and let \(v'_{j+1} v_j\) is oriented from \(v'_{j+1}\) to \(v_j\).

It is easy to see the orientation D has no odd directed cycle, by Lemma 1.1, D is an AT-orientation, note that every vertex \(x \in V(G_{R_n})\) has outdegree at most 3, so \(AT(G_{R_n}) \le 4\) (see Figure 10 (a) for n = 4, (b) for n = 5).

Figure 10. (a) An orientation of \(G_{R_4}\) and (b) for \(G_{R_5}\).

Corollary 3.1. The gyroelongated rotunda \(G_{R_n}\) is not chromatic-AT choosable, where \(n \geq 3\).

Corollary 3.2. For a gyroelongated rotunda \(G_{R_n}\),

\[ch(G_{R_n}) = 4.\]

Proof. Since \(\chi(G_{R_n}) \leq ch(G_{R_n}) \leq AT(G_{R_n})\), it can be conclude that \(ch(G_{R_n}) = 4\) when \(n \equiv 1\) or \(2 \pmod 3\).

When \(n \equiv 0 \pmod 3\), we can give a 3-list assignment L of \(G_{R_n}\) using colors 0, 1, 2 and 3 as follows. Let \(L(v_j) = L(v_j') = L(u_i') = \{0,1,2\}\) for \(i=1,2,\ldots,n, j=1,2,\ldots,2n;\) and \(L(u_1) = \{1,2,3\}, \ L(u_k) = \{0,1,3\}\) for \(k=2,\ldots,n.\) Without loss of generality, let \(\phi(v_1') = 0\), \(\phi(v_2') = 1\), by Lemma 3.1, \(\phi(u_1') = 1\), \(\phi(u_2') = 0\) and \(\phi(u_n') = 2\). Since \(u_1\) is adjacent to \(u_1', u_n'\), and \(u_2\) is adjacent to \(u_1', u_2'\), we have \(\phi(u_1) = \phi(u_2) = 3\), that a contradiction. It is an improper L-colouring of \(G_{R_n}\), so \(ch(G_{R_n}) = 4\) when \(n \equiv 0 \pmod 3\) (see Figure 11 for n = 3).

Figure 11. An improper 3-list colouring of \(G_{R_3}\).

4. Conclusion

In this article, we obtain the exact value of the Alon-Tarsi number of cupolarotundas \(R_{Q_n}^I, R_{Q_n}^{II}\), and gyroelongated rotunda \(G_{R_n}\) by using the AT-orientation skill. Additionally, cupolarotundas \(R_{Q_n}^I\) and \(R_{Q_n}^{II}\) are chromatic-AT choosable, but the gyroelongated rotunda \(G_{R_n}\) is not chromatic-AT choosable.

5. Acknowledgement

The authors would like to thank the Editor and the anonymous referees for their helpful comments and suggestions. This work was partially funded by Science and Technology Project of Hebei Education Department, China (No. ZD2020130) and the Natural Science Foundation of Hebei Province, China (No. A2021202013).

References

• [1] N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica, 12 (2) (1992), 125–134
• [2] B. Grünbaum, Graphs of polyhedra; polyhedra as graphs, Discrete Math. 307 (3) (2005), 445–463.
• [3] J. Grytczuk and X.D. Zhu, The Alon-Tarsi number of planar graphs minus a matching, J. Combin. Theory Ser. B, 145 (2020), 511–520.
• [4] T.R. Jensen and B. Toft, Graph coloring problems, Wiley, New York, 1995.
• [5] H. Kaul and J.A. Mudrock, On the Alon-Tarsi number and chromatic choosability of Cartesian products of graphs, Electron. J. Combin, 26 (1) (2019), #P1.3.
• [6] R. Kim, S. Kim, and X.D. Zhu, The Alon-Tarsi number of subgraphs of a planar graph, arXiv preprint arXiv:1906.01506.

• [7] Z.G. Li, Z.L. Shao, F. Petrov, and A. Gordeev, The Alon-Tarsi number of toroidal grids, Eur. J. Combin., 111 (2023), 103697.
• [8] Z.G. Li, Q. Ye, and Z.L. Shao, The Alon-Tarsi number of Halin graphs, Appl. Math. J Chinese Univ. Ser. A, 38 (3) (2023), 373–378.
• [9] H.T. Lu and X.D. Zhu, The Alon-Tarsi number of planar graphs without cycles and lengths 4 and l, Discrete Math. 343 (5) (2020), 111797.
• [10] X.D. Zhu, The Alon-Tarsi number of planar graphs, J. Combin. Theory Ser. B, 134 (2019), 354–358.
• [11] X.D. Zhu and R. Balakrishnan, Combinatorial Nullstellensatz With Applications to Graph Colouring, Chapman and Hall/CRC, 2021.