The 4-Choosability of Plane Graphs without 4-Cycles

Peter Che Bor Lam; Baogang Xu; Jiazhuang Liu

doi:10.1006/jctb.1998.1893

The 4-Choosability of Plane Graphs without 4-Cycles

Peter Che Bor Lam^*, Baogang Xu, Jiazhuang Liu

^*Corresponding author for this work

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

61 Citations (Scopus)

Abstract

A graphGis calledk-choosable ifkis a number such that if we give lists ofkcolors to each vertex ofGthere is a vertex coloring ofGwhere each vertex receives a color from its own list no matter what the lists are. In this paper, it is shown that each plane graph without 4-cycles is 4-choosable.

Original language	English
Pages (from-to)	117-126
Number of pages	10
Journal	Journal of Combinatorial Theory. Series B
Volume	76
Issue number	1
DOIs	https://doi.org/10.1006/jctb.1998.1893
Publication status	Published - May 1999
Externally published	Yes

Scopus Subject Areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

User-Defined Keywords

4-cycle
Choosability
List coloring
Plane graph

Access to Document

10.1006/jctb.1998.1893

Cite this

@article{e9ad69d3ade943c2b69547fc52beaf1c,

title = "The 4-Choosability of Plane Graphs without 4-Cycles",

abstract = "A graphGis calledk-choosable ifkis a number such that if we give lists ofkcolors to each vertex ofGthere is a vertex coloring ofGwhere each vertex receives a color from its own list no matter what the lists are. In this paper, it is shown that each plane graph without 4-cycles is 4-choosable.",

keywords = "4-cycle, Choosability, List coloring, Plane graph",

author = "{Che Bor Lam}, Peter and Baogang Xu and Jiazhuang Liu",

note = "Funding Information: Research is partially supported by Research Grant Council, Hong Kong; by Faculty Research Grant, Hong Kong Baptist University and by the Doctoral Foundation of the Education Commission of the The People{\textquoteright}s Republic of China.",

year = "1999",

month = may,

doi = "10.1006/jctb.1998.1893",

language = "English",

volume = "76",

pages = "117--126",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - The 4-Choosability of Plane Graphs without 4-Cycles

AU - Che Bor Lam, Peter

AU - Xu, Baogang

AU - Liu, Jiazhuang

N1 - Funding Information: Research is partially supported by Research Grant Council, Hong Kong; by Faculty Research Grant, Hong Kong Baptist University and by the Doctoral Foundation of the Education Commission of the The People’s Republic of China.

PY - 1999/5

Y1 - 1999/5

N2 - A graphGis calledk-choosable ifkis a number such that if we give lists ofkcolors to each vertex ofGthere is a vertex coloring ofGwhere each vertex receives a color from its own list no matter what the lists are. In this paper, it is shown that each plane graph without 4-cycles is 4-choosable.

AB - A graphGis calledk-choosable ifkis a number such that if we give lists ofkcolors to each vertex ofGthere is a vertex coloring ofGwhere each vertex receives a color from its own list no matter what the lists are. In this paper, it is shown that each plane graph without 4-cycles is 4-choosable.

KW - 4-cycle

KW - Choosability

KW - List coloring

KW - Plane graph

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

U2 - 10.1006/jctb.1998.1893

DO - 10.1006/jctb.1998.1893

M3 - Journal article

AN - SCOPUS:0000582513

SN - 0095-8956

VL - 76

SP - 117

EP - 126

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

The 4-Choosability of Plane Graphs without 4-Cycles

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this