The Alon-Tarsi number of two kinds of planar graphs

Zhiguo Li, Qing Ye, Zeling Shao

Abstract


The Alon-Tarsi number AT(G) of a graph G is the least k for which there is an orientation D of G with max outdegree k − 1 such that the number of spanning Eulerian subgraphs of G with an even number of edges differs from the number of spanning Eulerian subgraphs with an odd number of edges. In this paper, the exact value of the Alon-Tarsi number of two kinds of planar graphs is obtained.


Keywords


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

Full Text:

PDF

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

References

V.G. Vizing, Vertex colorings with given colors, Metody Diskret. Anal. 29 (1976), 3–10.

P. Erds, A.L. Rubin, and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979), 126–157.

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

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

U. Schauz, A paintability version of the Combinatorial Nullstellensatz and list colorings of k-partite k-uniform hypergraphs, Electron. J. Combin. 17(1) (2010), 3940–3946.

X.D. Zhu, On-line list coloring of graphs, Electron. J. Combin. 16(1) (2009), R127.

C. Thomassen, Every planar graph is 5-choosable, J. Combin. Theory Ser. B 62(1) (1994), 180–181.

M. Voigt and B. Wirth, On 3-colorable non-4-choosable planar graphs, J. Graph Theory 24(3) (1997), 233–235.

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

Z.G. Li, Q. Ye, and Z.L. Shao, The Alon-Tarsi number of Halin graphs, arXiv preprint arXiv:2110.11617.

L. Zhang, H.Y. Chen, and X.Y. Yuan, The adjacent vertex distinguishing incidence coloring numbers of a class of 4-regular planar graphs, Math. Pract. Theory 42 (19) (2012), 197–201.

M. Pankov and A. Tyc, On two types of Z-monodromy in triangulations of surfaces, Discrete Math. 342 (9) (2019), 2549–2558.

D. Hefetz, On two generalizations of the Alon-Tarsi polynomial method, J. Combin. Theory Ser. B 101 (6) (2011), 403–414.

N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8(1-2) (1999), 7–29.

J. Hladký, D. Král, and U. Schauz, Brooks’ theorem via the Alon-Tarsi theorem, Discrete Math. 310 (23) (2010), 3426–3428.

U. Schauz, Algebraically solvable problems: describing polynomials as equivalent to explicit solutions, Electron. J. Combin. 15(1) (2008), 273–295.


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