Electronic Journal of Graph Theory and Applications 12 .
, 205Ae217 The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo LiO .
Yujia Gai.
Zeling Shao Department of Mathematics.
Hebei University of Technology.
China zhiguolee@hebut.
cn, 202221101013@stu.
cn, zelingshao@163.
Abstract 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 Oe 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.
Introduction We only consider simple and finite graphs in this paper.
The chromatic number of a graph G, denoted by N(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.
of k permissible colors.
An L-coloring of G is a coloring f of G such that f .
OO L.
for each vertex 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 Oe dH .
of every vertex v of H in H is equal to its outdegree d H .
We do not assume that H Received: 30 November 2023.
Revised: 17 June 2024.
Accepted: 23 June 2024.
The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
is connected.
H is even if it has an even number of edges, otherwise, it is odd.
Let Ee (D) and Eo (D) denote the family of even and odd Eulerian subgraphs of D, respectively.
Let diff(D) = |Ee (D)| Oe |Eo (D)|.
We say that D is Alon-Tarsi if diff(D) = 0.
If an orientation D of G yields an Alon-Tarsi digraph, then we say D is an Alon-Tarsi orientation (AT -orientation, for shor.
of G .
The Alon-Tarsi number of G (AT (G), for shor.
is the smallest k so that there exists an orientation D of G with max outdegree k Oe 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 .
, subsequently, they used algebraic methods to prove that N(G) O ch(G) O AT (G).
The graph G is called chromatic-choosable if N(G) = ch(G).
The graph G is called chromaticAT choosable if N(G) = AT (G).
There are some results concerning the Alon-Tarsi number of planar graphs.
Zhu .
showed that every planar graph G has AT (G) O 5.
Grytczuk and Zhu proved that every planar graph G has a matching M such that AT (G Oe M ) O 4 in .
Zhu and Kim also showed that every planar graph G has a forest F such that AT (G Oe E(F )) O 3 in .
Zhu and Lu .
used the discharging method to show that for l OO .
, 6, .
, every graph G OO P4,l has a matching M such that G Oe M has the Alon-Tarsi number at most 3 which P4,l means the family of planar graphs with no cycles of length 4 and l.
The first author and Ye et al proved that a Halin graph H has the Alon-Tarsi number 4 when it is a wheel of even order and 3 otherwise in .
There are also some conclusions for special graphs.
Zhu and Balakrishnan .
proved that |E(H)| UO 1, they also showed that bipartite planar bipartite graph G has AT (G) = maxHOCG UO |V (H)| graphs G have AT (G) O 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 .
Suppose that G is a complete graph or an odd cycle with |V (G)| Ou 3.
Suppose H is a graph on at least two vertices that contains a Hamilton path O1 .
O2 , .
On , such that Oi has at most k neighbors among O1 .
O2 , .
OiOe1 .
Kaul.
Mudrock .
also proved the Cartesian product of G and H has AT (GnH) O OI(G) k.
The first author and Shao et al.
proved that the Cartesian product of Cm and Cn has the Alon-Tarsi number 4 when n and m are both odd and 3 otherwise in .
A graph G is a polyhedral graph if G is isomorphic to the 1-skeleton of a three-dimensional convex polyhedron P .
According to SteinitzAos theorem .
, 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 Qn 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 RQ is an infinite set of polyhedra, constructed by adjoining an n-gonal cupola to a 2n-gonal rotunda .
ee Figure 1 .
for n = .
For n Ou 3, a RQ 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 The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
G, it is easy to see |V (RQ )| = 9n and |E(RQ )| = 17n.
The second cupolarotunda RQ is an infinite set of polyhedra, constructed by adjoining an n-gonal rotunda to a 2n-gonal cupola .
ee has 4n triangles, 2n squares, n pentagons, an n-gonal Figure 1 .
for n = .
For n Ou 3, a RQ and a 4n-gonal as faces, and |V (RQn )| = 8n, |E(RQ )| = 15n.
Figure 1.
A cupolarotunda RQ and .
a cupolarotunda RQ Antiprism also plays an important role in polyhedral graphs.
The gyroelongated rotunda GRn is an infinite set of polyhedra, constructed by adjoining an n-gonal rotunda to a 2n-gonal antiprism .
ee Figure 2 for n = .
For n Ou 3, a gyroelonged rotunda has 6n triangles, n pentagons, an n-gonal and a 2n-gonal as faces, and |V (GRn )| = 6n, |E(GRn )| = 13n.
Figure 2.
Gyroelongated rotunda GR3 .
Lemma 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 RQ and gyroelongated rotunda GRn .
The main results are the following theorems:
The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
Theorem 1.
For cupolarotundas RQ and RQ , we have AT (RQ ) = AT (RQ ) = 3.
Theorem 2.
For a gyroelongated rotunda GRn , we have AT (GRn ) = 4.
The Proof of the Theorem 1 Assume V (RQ ) = .
1 , u2 , .
, un , v1 , v2 , .
, v2n , v1A , v2A , .
, v2n , w1 , w2 , .
, w4n }.
The top cycle u1 u2 A A A un u1 is called C1 , the middle cycle v1 v2 A A A v2n v1 is called C2 and the bottom cyA are points located between C2 and cle w1 w2 A A A w4n w1 is called C3 .
the vertices v1A , v2A , .
, v2n C3 .
For i = 1, .
, n, the vertices ui v2i v2iOe1 form a triangle and ui ui 1 v2i 1 v2i form a quadranA For j = 1, .
, 2n, the vertices vj vj vj 1 form a triangle, vj w2j w2jOe1 form a triangle and A A vj vj 1 vj 1 w2j 1 w2j form a pentagon .
ee Figure .
The proof of Theorem 1 will be completed by the following lemmas.
Lemma 2.
For a cupolarotunda RQ ) = 3.
N(RQ
) Ou 3.
It remains contains a triangle as its subgraph, hence N(RQ Proof.
It is easily seen that RQ to show that N(RQn ) O 3.
It suffices to show that i: V (RQn ) Ie .
, 1, .
is a proper 3-coloring of Case 1.
n is even.
For the vertices in C1 , let i.
1 ) = 2.
For i = 2, .
, n, let i.
i ) = 1 when i is an odd number and i.
i ) = 0 when i is an even number.
For the vertices in C2 , for j = 1, .
, 2n, let i.
j ) = 0 or 1 when j is an even number.
Therefore, for i = 2, .
, n, if i.
i ) = 1, then i.
2i ) = 0, i.
2iOe1 ) = 2.
if i.
i ) = 0, then i.
2i ) = 1, i.
2iOe1 ) = 2.
Since n is even, we have i.
n ) = 0, i.
2n ) = 1.
the neighbours of v1 are u1 , v2n , and u1 v1 v2 form a triangle, it is easy to know that i.
1 ) = 0, i.
2 ) = 1.
Then i.
jA ) can be determined in a unique way.
For the vertices in C3 , for j = 1, .
, 2n, the neighbours of vjA are vj , vj 1 , w2j , w2jOe1 .
Let i.
j ) = i.
2j ), i.
j 1 ) = i.
2jOe1 ) when j is an even number and let i.
j ) = i.
2jOe1 ), i.
j 1 ) = i.
2j ) when j is an odd number.
We can know that i is a proper coloring of RQ Case 2.
n is odd.
This is similar to what happens in case 1.
Since n is odd, we have i.
n ) = 1, i.
2n ) = 0.
the neighbours of v1 are u1 , v2n , and u1 v1 v2 form a triangle, it is easy to know that i.
1 ) = 1, i.
2 ) = 0.
The other points are colored in the same way in case 1, we can know that i is a proper coloring of RQ (See Figure 3 .
for n = 4,.
for n = .
Hence N(RQn ) O 3.
The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
for RQ Figure 3.
A proper 3-coloring of RQ Lemma 2.
For a cupolarotunda RQ
AT (RQ
) = 3.
) O 3.
) = 3.
What is left is to show that AT (RQ ) Ou N(RQ Proof.
By Lemma 2.
AT (RQ
denote L.
as the set of edges belonging to quadrangles connecting C1 and C2 .
an orientation D.
The rules of orientation D are as follows:
We give RQ R1: For the cycles C2 .
C3 are clockwise.
For the cycle C1 , u1 u2 is oriented from u2 to u1 , ui ui 1 is oriented from ui to ui 1 .
= 2, .
, .
R2: The edges belonging to L.
are oriented from C2 to C1 .
R3: For j = 1, 2, .
, 2n, let vj vjA , vj 1 vjA are oriented from vjA to vj , vj 1 and let the edges A vj w2j , vjA w2jOe1 are oriented from w2j , w2jOe1 to vjA .
Since the orientation D has no odd directed cycle, by Lemma 1.
D is an AT -orientation, and it is easy to see that every vertex x OO V (RQ ) has outdegree at most 2, so AT (RQ ) O 3 .
ee Figure 4 .
for n = 4,.
for n = .
Assume V (RQ ) = .
1 , v2 , .
, vn , v1A , v2A , .
, vnA , u1 , u2 , .
, u2n , w1 , w2 , .
, w4n }.
The top cycle v1 v2 .
vn v1 is called C1 , the middle cycle u1 u2 .
u2n u1 is called C2 and the bottom cycle w1 w2 .
w4n w1 is called C3 .
the vertices v1A , v2A , .
, vnA are points located between C1 and C2 .
For A A A A i = 1, .
, n, the vertices vi vi vi 1 form a triangle, vi u2i u2iOe1 form a triangle and vi vi 1 vi 1 u2i 1 u2i form a pentagon.
For j = 1, .
, 2n, uj w2j w2jOe1 form a triangle and uj uj 1 w2j 1 w2j form a quadrangle .
ee Figure .
Lemma 2.
For a cupolarotunda RQ
N(RQ
) = 3.
The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
for RQ Figure 4.
An orientation of RQ ) Ou 3.
It remains contains a triangle as its subgraph, hence N(RQ Proof.
It is easily seen that RQ to show that N(RQn ) O 3.
It suffices to show that i: V (RQn ) Ie .
, 1, .
is a proper 3-coloring of Case 1.
n O 0 .
For the vertices in C3 .
For k = 1, 2, .
, 4n, let i.
k ) = 0 if k O 1 .
let i.
k ) = 1 if k O 2 .
and let i.
k ) = 2 if k O 0 .
The coloring of the remaining vertices can be uniquely determined.
For the vertices in C2 .
For j = 1, 2, .
, 2n, since uj w2j w2jOe1 form a triangle, we have i.
j ) = 2 if j O 1 .
j ) = 1 if j O 2 .
and i.
j ) = 0 if j O 0 .
For i = 1, 2, .
, n, since viA u2i u2iOe1 form a triangle, we have i.
iA ) = 0 if i O 1 .
iA ) = 1 if i O 2 .
and i.
iA ) = 2 if i O 0 .
For the vertices in C1 .
Since vi is adjacent viA , viOe1 , hence i.
i ) = 1 if i O 1 .
i ) = 2 if i O 2 .
and i.
i ) = 0 if i O 0 .
ee Figure 5 .
for n = .
Case 2.
n O 1 .
For the vertices in C1 , let i.
n ) = 1.
For i = 1, 2, .
, n Oe 1, let i.
i ) = 0 if i O 1 .
i ) = 1 if i O 2 .
and let i.
i ) = 2 if i O 0 .
Let i.
nOe1 ) = 0, i.
nA ) = 2.
For i = 1, 2, .
, n Oe 2, let i.
iA ) = 2 if i O 1 .
iA ) = 0 if i O 2 .
and let i.
iA ) = 1 if i O 0 .
For the vertices in C2 , note that viA is adjacent vi , vi 1 , u2i , u2iOe1 .
When n is an even number, for i = 1, 2, .
, n, let i.
i ) = i.
2i ), i.
i 1 ) = i.
2iOe1 ) when i is an even number and i.
i 1 ) = i.
2i ), i.
i ) = i.
2iOe1 ) when i is an odd number.
When n is an odd number, let i.
2n ) = 1, i.
2nOe1 ) = 0 and for i = 1, 2, .
, n Oe 1, let i.
i ) = i.
2i ), i.
i 1 ) = i.
2iOe1 ) when i is an even number and i.
i 1 ) = i.
2i ), i.
i ) = i.
2iOe1 ) when i is an odd number.
For the vertices in C3 , we know that u2i is adjacent w4i , w4iOe1 and u2iOe1 is adjacent w4iOe2 , w4iOe3 .
The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
When n is an odd number, let i.
4nOe7 ) = 2, i.
4nOe6 ) = i.
4nOe4 ) = 0, i.
4nOe5 ) = 1.
For i = 1, 2, .
, n Oe 2, n, let i.
iA ) = i.
4iOe1 ) = i.
4iOe3 ) when i is an even number and i.
iA ) = i.
4i ) = i.
4iOe2 ) when i is an odd number.
When n is an even number, for i = 1, 2, .
, n, let i.
iA ) = i.
4iOe1 ) = i.
4iOe3 ) when i is an even number and i.
iA ) = i.
4i ) = i.
4iOe2 ) when i is an odd number .
ee Figure 5 .
for n = 4.
Figure 7 .
for n = .
Figure 5.
A proper 3-coloring of RQ and .
for RQ Case 3.
n O 2 .
This is similar to what happens in case 2.
For the vertices in C1 , let i.
nOe1 ) = 1, i.
n ) = 2.
The other points are colored in the same way as C1 in case 2, it is easy to know that i.
iA ) is colored in a unique way .
= 1, .
, .
For the vertices in C2 , let i.
2n ) = 2, i.
2nOe1 ) = 0.
The other points are colored in the same way as C2 in case 2.
For the vertices in C3 .
When n is an even number, let i.
4nOe9 ) = 1, i.
4nOe8 ) = i.
4nOe10 ) = 0,i.
4nOe11 ) = 2 and for i = 1, 2, .
, n Oe 3, n Oe 1, n, i.
4i ), i.
4iOe1 ), i.
4iOe2 ), i.
4iOe3 ) are similar to C3 in case 2.
When n is an odd number, let i.
4n ) = 0, i.
4nOe1 ) = i.
4nOe3 ) = 1, i.
4nOe2 ) = 2 and let i.
4nOe4 ) = i.
4nOe6 ) = 0, i.
4nOe5 ) = 2, i.
4nOe7 ) = 1 and for i = 1, 2, .
, n Oe 2, i.
4i ), i.
4iOe1 ), i.
4iOe2 ), i.
4iOe3 ) are similar to C3 in case 2 .
ee Figure 6 .
for n = 5.
Figure 7 .
for n = .
Lemma 2.
For a cupolarotunda RQ
AT (RQ
) = 3.
Proof.
By Lemma 2.
AT (RQ
) Ou N(RQ ) = 3.
What is left is to show that AT (RQ ) O 3, the orientation method is similar to RQn .
Since the orientation D has no odd directed cycle, by Lemma 1.
D is an AT -orientation and it is easy to see that every vertex x OO V (RQ ) has outdegree at most 2, so AT (RQn ) O 3 .
ee Figure 6 .
for n = .
The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
Figure 6.
A proper 3-coloring of RQ and .
an orientation of RQ Figure 7.
Local points coloring of RQ and .
for RQ The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
Corollary 2.
Cupolarotundas RQ and RQ are chromatic-AT choosable, where n Ou 3.
The Proof of the Theorem 2 Assume V (GRn ) = .
1 , u2 , .
, un , uA1 , uA2 , .
, uAn , v1 , v2 , .
, v2n , v1A , v2A , .
, v2n The top cycle u1 u2 A A A un u1 is called C1 , the middle cycle v1 v2 A A A v2n v1 is called C2 and the bottom cycle A v1A is called C3 .
the vertices uA1 , uA2 , .
, uA2n are points located between C1 and C2 .
For v1A v2A A A A v2n i = 1, .
, n, the vertices ui ui ui 1 form a triangle, ui v2i v2iOe1 form a triangle and ui ui 1 ui 1 v2i 1 v2i form a pentagon.
For j = 1, .
, 2n, vj vj 1 vj 1 form a triangle and vj vjA vj 1 form a triangle .
ee Figure .
The proof of Theorem 2 will be completed by the following lemmas.
Lemma 3.
For a gyroelongated rotunda GRn , 3, if n O 0 .
N(GRn ) = 4, otherwise.
Proof.
It is easy to see that GRn contains a triangle as its subgraph, hence N(GRn ) Ou 3.
By the Four-Color Theorem.
N(GRn ) O 4.
Let i: V (GRn ) Ie .
, 1, .
Without loss of generality, let i.
1A ) = 0 and i.
2A ) = 1, it is a simA ple matter to obtain the colors of v1 , .
, v2n , v3A , .
, v2n in a unique way.
For q = 0, 1, .
UO 2n
UU,
we have i.
3q 1 ) = 0, i.
3q 2 ) = 1, i.
3q 3 ) = 2 and i.
3q 1 ) = 2, i.
3q 2 ) = 0, i.
3q 3 ) = 1.
Case 1.
n O 1 .
) = 1,i.
2n ) = 0.
When n O 1 .
, 2n O 2 .
By the above rule, we have i.
2n A A It is easy to see that v2n is the neighbor of v1 , but i.
1 ) = 0, that a contradiction.
Hence it is not 3-colorable .
ee Figure 8 .
for n = .
Case 2.
n O 2 .
) = 0,i.
2n ) = 2.
When n O 2 .
, 2n O 1 .
By the above rule, we have i.
2n A A A Note that v2n is adjacent to v1 , but i.
1 ) = 0, that a contradiction.
Hence it is not 3-colorable .
ee Figure 8 .
for n = .
Case 3.
n O 0 .
When n O 0 .
, 2n O 0 .
, we can give a 3-coloring as follows:
For q = 0, 1, .
UO 2n UU, let i.
3q 1 ) = 0, i.
3q 2 ) = 1, i.
3q 3 ) = 2 and let i.
3q 1 ) = 2, i.
3q 2 ) = 0, i.
3q 3 ) = 1.
For p = 0, 1, .
UO n3 UU, let i.
A3p 1 ) = 1, i.
A3p 2 ) = 0, i.
A3p 3 ) = 2 and let i.
3p 1 ) = 0, i.
3p 2 ) = 2, i.
3p 3 ) = 1.
It is a proper 3-coloring .
ee Figure 9 for n = 3 ).
Lemma 3.
For a gyroelongated rotunda GRn .
AT (GRn ) = 4.
Proof.
The GRn has 6n vertices and 13n edges.
Since xOOV (D) d D .
= |A(D)|, by the Pigeonhole Principle, there exists some vertices have outdegree at least 3 for any orientation D of GRn .
Hence AT (GRn ) Ou 4.
What is left is to show that AT (GRn ) O 4.
The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
Figure 8.
An improper 3-coloring of GR4 and .
for GR5 .
Figure 9.
A proper 3-colouring of GR3 .
The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
We give GRn an orientation D.
The rules of orientation D are given as following:
R1: For the cycles C2 .
C3 are clockwise.
For the cycle C1 , u1 u2 is oriented from u2 to u1 , ui ui 1 is oriented from ui to ui 1 .
= 2, .
, .
R2: For i = 1, 2, .
, n, let the edges uAi ui , uAi ui 1 are oriented from uAi to ui , ui 1 and let uAi v2i .
A ui v2iOe1 are oriented from v2i , v2iOe1 to uAi .
R3: For j = 1, 2, .
, 2n, let the edges vjA vj is oriented from vjA to vj and let vj 1 vj is oriented A from vj 1 to vj .
It is easy to see the orientation D has no odd directed cycle, by Lemma 1.
D is an AT -orientation, note that every vertex x OO V (GRn ) has outdegree at most 3, so AT (GRn ) O 4 .
ee Figure 10 .
for n = 4,.
for n = .
Figure 10.
An orientation of GR4 and .
for GR5 .
Corollary 3.
The gyroelongated rotunda GRn is not chromatic-AT choosable, where n Ou 3.
Corollary 3.
For a gyroelongated rotunda GRn , ch(GRn ) = 4.
Proof.
Since N(GRn ) O ch(GRn ) O AT (GRn ), it can be conclude that ch(GRn ) = 4 when n O 1 or 2 .
When n O 0 .
, we can give a 3-list assignment L of GRn using colors 0, 1, 2 and 3 as follows.
Let L.
j ) = L.
jA ) = L.
Ai ) = .
, 1, .
for i = 1, 2, .
, n, j = 1, 2, .
, 2n.
1 ) = .
, 2, .
k ) = .
, 1, .
for k = 2, .
, n.
Without loss of generality, let i.
1A ) = 0, i.
2A ) = 1, by Lemma 3.
1, i.
A1 ) = 1, i.
A2 ) = 0 and i.
An ) = 2.
Since u1 is adjacent to uA1 , uAn , and u2 is adjacent to uA1 , uA2 , we have i.
1 ) = i.
2 ) = 3, that a contradiction.
It is an improper L-colouring of GRn , so ch(GRn ) = 4 when n O 0 .
ee Figure 11 for n = 3 ).
The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda Zhiguo Li et al.
Figure 11.
An improper 3-list colouring of GR3 .
Conclusion ,RQ In this article, we obtain the exact value of the Alon-Tarsi number of cupolarotundas RQ and gyroelongated rotunda GRn by using the AT -orientation skill.
Additionally, cupolarotundas and RQ are chromatic-AT choosable, but the gyroelongated rotunda GRn is not chromaticn AT choosable.
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.
ZD2020.
and the Natural Science Foundation of Hebei Province.
China (No.
A2021202.
References