The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda

Zhiguo Li, Yujia Gai, Zeling Shao

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 - 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

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2024.12.2.5

References

N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica, 12 (2) (1992), 125–134.

B. Grünbaum, Graphs of polyhedra; polyhedra as graphs, Discrete Math. 307 (3) (2005), 445–463.

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.

T.R. Jensen and B. Toft, Graph coloring problems, Wiley, New York, 1995.

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.

R. Kim, S. Kim, and X.D. Zhu, The Alon-Tarsi number of subgraphs of a planar graph, arXiv preprint arXiv:1906.01506.

Z.G. Li, Z.L. Shao, F. Petrov, and A. Gordeev, The Alon-Tarsi number of toroidal grids, Eur. J. Combin., 111 (2023), 103697.

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.

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.

X.D. Zhu, The Alon-Tarsi number of planar graphs, J. Combin. Theory Ser. B, 134 (2019), 354–358.

X.D. Zhu and R. Balakrishnan, Combinatorial Nullstellensatz With Applications to Graph Colouring, Chapman and Hall/CRC, 2021.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats