Choosability with separation of planar graphs without prescribed cycles

Min Chen; Yingying Fan; André Raspaud; Wai Chee Shiu; Weifan Wang

doi:10.1016/j.amc.2019.124756

Choosability with separation of planar graphs without prescribed cycles

Min Chen^*, Yingying Fan, André Raspaud, Wai Chee Shiu, Weifan Wang

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

2 Citations (Scopus)

Abstract

In terms of constraining the list assignment, one refinement of k-choosability is considered as choosability with separation. We call a graph (k, d)-choosable if it is colorable from lists of size k where adjacent vertices have at most d common colors in their lists. If two cycles have exactly one common edge, then they are said to be normally adjacent.

In this article, it is shown that planar graphs without 5-cycles and normally adjacent 4-cycles are (3,1)-choosable. This extends a result that planar graphs without 5- and 6-cycles are (3,1)-choosable (Choi et al. (2016))

Original language	English
Article number	124756
Journal	Applied Mathematics and Computation
Volume	367
DOIs	https://doi.org/10.1016/j.amc.2019.124756
Publication status	Published - 15 Feb 2020

Scopus Subject Areas

Computational Mathematics
Applied Mathematics

User-Defined Keywords

Adjacent cycles
Choosability with separation
List coloring
Planar graphs

Access to Document

10.1016/j.amc.2019.124756

Cite this

@article{72d9342d471240d5a63c532836a44cea,

title = "Choosability with separation of planar graphs without prescribed cycles",

abstract = "In terms of constraining the list assignment, one refinement of k-choosability is considered as choosability with separation. We call a graph (k, d)-choosable if it is colorable from lists of size k where adjacent vertices have at most d common colors in their lists. If two cycles have exactly one common edge, then they are said to be normally adjacent.In this article, it is shown that planar graphs without 5-cycles and normally adjacent 4-cycles are (3,1)-choosable. This extends a result that planar graphs without 5- and 6-cycles are (3,1)-choosable (Choi et al. (2016))",

keywords = "Adjacent cycles, Choosability with separation, List coloring, Planar graphs",

author = "Min Chen and Yingying Fan and Andr{\'e} Raspaud and Shiu, {Wai Chee} and Weifan Wang",

note = "Funding Information: Research supported by ZJNSFC (No.LY19A010015), NSFC (No.11971437), (11771402) and FRG, Hong Kong Baptist University. Publisher copyright: {\textcopyright} 2019 Elsevier Inc.",

year = "2020",

month = feb,

day = "15",

doi = "10.1016/j.amc.2019.124756",

language = "English",

volume = "367",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Choosability with separation of planar graphs without prescribed cycles

AU - Chen, Min

AU - Fan, Yingying

AU - Raspaud, André

AU - Shiu, Wai Chee

AU - Wang, Weifan

PY - 2020/2/15

Y1 - 2020/2/15

N2 - In terms of constraining the list assignment, one refinement of k-choosability is considered as choosability with separation. We call a graph (k, d)-choosable if it is colorable from lists of size k where adjacent vertices have at most d common colors in their lists. If two cycles have exactly one common edge, then they are said to be normally adjacent.In this article, it is shown that planar graphs without 5-cycles and normally adjacent 4-cycles are (3,1)-choosable. This extends a result that planar graphs without 5- and 6-cycles are (3,1)-choosable (Choi et al. (2016))

AB - In terms of constraining the list assignment, one refinement of k-choosability is considered as choosability with separation. We call a graph (k, d)-choosable if it is colorable from lists of size k where adjacent vertices have at most d common colors in their lists. If two cycles have exactly one common edge, then they are said to be normally adjacent.In this article, it is shown that planar graphs without 5-cycles and normally adjacent 4-cycles are (3,1)-choosable. This extends a result that planar graphs without 5- and 6-cycles are (3,1)-choosable (Choi et al. (2016))

KW - Adjacent cycles

KW - Choosability with separation

KW - List coloring

KW - Planar graphs

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

U2 - 10.1016/j.amc.2019.124756

DO - 10.1016/j.amc.2019.124756

M3 - Journal article

AN - SCOPUS:85072700394

SN - 0096-3003

VL - 367

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

M1 - 124756

ER -

Choosability with separation of planar graphs without prescribed cycles

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this