On structure of some plane graphs with application to choosability

Peter Che Bor Lam*, Wai Chee SHIU, Baogang Xu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)

Abstract

A graph G=(V, E) is (x, y)-choosable for integers x>y≥1 if for any given family {A(v)|v∈V} of sets A(v) of cardinality x, there exists a collection {B(v)|v∈V} of subsets B(v)⊂A(v) of cardinality y such that B(u)∩B(v)=Ø whenever uv∈E(G). In this paper, structures of some plane graphs, including plane graphs with minimum degree 4, are studied. Using these results, we may show that if G is free of k-cycles for some k∈{3, 4, 5, 6}, or if any two triangles in G have distance at least 2, then G is (4m, m)-choosable for all nonnegative integers m. When m=1, (4m, m)-choosable is simply 4-choosable. So these conditions are also sufficient for a plane graph to be 4-choosable.

Original languageEnglish
Pages (from-to)285-296
Number of pages12
JournalJournal of Combinatorial Theory. Series B
Volume82
Issue number2
DOIs
Publication statusPublished - Jul 2001

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

User-Defined Keywords

  • Choosable; plane graph; cycle; triangle

Fingerprint

Dive into the research topics of 'On structure of some plane graphs with application to choosability'. Together they form a unique fingerprint.

Cite this