Plane graphs with maximum degree 9 are entirely 11-choosable

Xiaoxue Hu; Weifan Wang; Wai Chee Shiu; Yiqiao Wang

doi:10.1016/j.disc.2016.05.015

Plane graphs with maximum degree 9 are entirely 11-choosable

Xiaoxue Hu, Weifan Wang, Wai Chee Shiu^*, Yiqiao Wang

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-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 language	English
Pages (from-to)	2742-2753
Number of pages	12
Journal	Discrete Mathematics
Volume	339
Issue number	11
DOIs	https://doi.org/10.1016/j.disc.2016.05.015
Publication status	Published - 6 Nov 2016

Scopus Subject Areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

User-Defined Keywords

Entire choosability
Maximum degree
Plane graph

Access to Document

10.1016/j.disc.2016.05.015

Cite this

@article{a38207629ff54a489bcc74e69758da3d,

title = "Plane graphs with maximum degree 9 are entirely 11-choosable",

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.",

keywords = "Entire choosability, Maximum degree, Plane graph",

author = "Xiaoxue Hu and Weifan Wang and Shiu, {Wai Chee} and Yiqiao Wang",

note = "Funding Information: Research supported by NSFC (Nos. 11371328 ; 11301035 ). ",

year = "2016",

month = nov,

day = "6",

doi = "10.1016/j.disc.2016.05.015",

language = "English",

volume = "339",

pages = "2742--2753",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "11",

}

TY - JOUR

T1 - Plane graphs with maximum degree 9 are entirely 11-choosable

AU - Hu, Xiaoxue

AU - Wang, Weifan

AU - Shiu, Wai Chee

AU - Wang, Yiqiao

N1 - Funding Information: Research supported by NSFC (Nos. 11371328 ; 11301035 ).

PY - 2016/11/6

Y1 - 2016/11/6

N2 - 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.

AB - 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.

KW - Entire choosability

KW - Maximum degree

KW - Plane graph

UR - http://www.scopus.com/inward/record.url?scp=84973904738&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2016.05.015

DO - 10.1016/j.disc.2016.05.015

M3 - Journal article

AN - SCOPUS:84973904738

SN - 0012-365X

VL - 339

SP - 2742

EP - 2753

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 11

ER -

Plane graphs with maximum degree 9 are entirely 11-choosable

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this