Plane graphs with maximum degree 9 are entirely 11-choosable

Xiaoxue Hu, Weifan Wang, Wai Chee SHIU*, Yiqiao Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

A plane graph G is entirely k-choosable if, for every list L of colors satisfying L(x)=k for all xϵV(G)∩E(G)∩F(G), there exists a coloring which assigns to each vertex, each edge and each face a color from its list so that any adjacent or incident elements receive different colors. It was known that every plane graph G with maximum degree Δ≥10 is entirely (Δ+2)-choosable. In this paper, we improve this result by showing that every plane graph G with Δ=9 is entirely 11-choosable.

Original languageEnglish
Pages (from-to)2742-2753
Number of pages12
JournalDiscrete Mathematics
Volume339
Issue number11
DOIs
Publication statusPublished - 6 Nov 2016

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Entire choosability
  • Maximum degree
  • Plane graph

Fingerprint

Dive into the research topics of 'Plane graphs with maximum degree 9 are entirely 11-choosable'. Together they form a unique fingerprint.

Cite this