Thomassen in 1994 published a famous proof of the fact that the choosability of a planar graph is at most 5. Zhu in 2019 generalized this result by showing that the same bound holds for Alon-Tarsi numbers of planar graphs. We present an alternative proof of that fact, derived from the results on decompositions of planar graphs into trees known as Schnyder woods. It turns out that Thomassen’s technique and our proof based on Schnyder woods have a lot in common. We discuss and explain the prominent role that counterclockwise 3-orientations play in proofs based on both these approaches.
@article{10_37236_11888,
author = {Jakub Kozik and Bartosz Podkanowicz},
title = {Schnyder woods and {Alon-Tarsi} number of planar graphs},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {1},
doi = {10.37236/11888},
zbl = {1535.05078},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11888/}
}
TY - JOUR
AU - Jakub Kozik
AU - Bartosz Podkanowicz
TI - Schnyder woods and Alon-Tarsi number of planar graphs
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/11888/
DO - 10.37236/11888
ID - 10_37236_11888
ER -
%0 Journal Article
%A Jakub Kozik
%A Bartosz Podkanowicz
%T Schnyder woods and Alon-Tarsi number of planar graphs
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11888/
%R 10.37236/11888
%F 10_37236_11888
Jakub Kozik; Bartosz Podkanowicz. Schnyder woods and Alon-Tarsi number of planar graphs. The electronic journal of combinatorics, Tome 31 (2024) no. 1. doi: 10.37236/11888
