EUVIMEDEUVIMED entdecken
Crossref

Local Girth Choosability of Planar Graphs

Luke Postle, Evelyne Smith-Roberge

Advances in Combinatorics · 2022

DOI: 10.19086/aic.2022.8 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Advances in Combinatorics, 2022. Verfasst von Luke Postle und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In 1994, Thomassen famously proved that every planar graph is 5-choosable, resolving a conjecture initially posed by Vizing and, independently, Erd˝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 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)| ≥ 3 for all v ∈ V(G); |L(v)| ≥ 4 for every vertex v contained in a 4-cycle; and |L(v)| ≥ 5 for every v contained in a triangle, then G admits an L-colouring.

Zitieren

APA

Postle, L., & Smith-Roberge, E. (2022). Local Girth Choosability of Planar Graphs. Advances in Combinatorics. https://doi.org/10.19086/aic.2022.8

Vancouver

Postle L, Smith-Roberge E. Local Girth Choosability of Planar Graphs. Advances in Combinatorics. 2022. doi:10.19086/aic.2022.8

BibTeX
@article{Postle2022,
  author = {Postle, Luke and Smith-Roberge, Evelyne},
  title = {Local Girth Choosability of Planar Graphs},
  journal = {Advances in Combinatorics},
  year = {2022},
  doi = {10.19086/aic.2022.8}
}
Kostenlos starten →