Local girth choosability of planar graphs
Advances in Combinatorics (2022)
Voir la notice de l'article provenant de la source Scholastica
arXiv
In 1994, Thomassen famously proved that every planar graph is 5-choosable, resolving a conjecture initially posed by Vizing and, independently, Erd\H{os}, Rubin, and Taylor in the 1970s. Later, Thomassen proved that every planar graph of girth at least five is 3-choosable. In this paper, we introduce the concept of a \emph{local girth list assignment}: a list assignment wherein the list size of a vertex depends not on the girth of the graph, but rather on the length of the shortest cycle in which the vertex is contained. We give a local list colouring theorem unifying the two theorems of Thomassen mentioned above. In particular, we show that if $G$ is a planar graph and $L$ is a list assignment for $G$ such that $|L(v)| \geq 3$ for all $v \in V(G)$; $|L(v)| \geq 4$ for every vertex $v$ contained in a 4-cycle; and $|L(v)| \geq 5$ for every $v$ contained in a triangle, then $G$ admits an $L$-colouring.
Luke Postle; Evelyne Smith-Roberge. Local girth choosability of planar graphs. Advances in Combinatorics (2022). http://geodesic.mathdoc.fr/item/ADVC_2022_a1/
@article{ADVC_2022_a1,
author = {Luke Postle and Evelyne Smith-Roberge},
title = {Local girth choosability of planar graphs},
journal = {Advances in Combinatorics},
year = {2022},
language = {en},
url = {http://geodesic.mathdoc.fr/item/ADVC_2022_a1/}
}