The 3-choosability of plane graphs of girth 4

Peter C.B. Lam*, Wai Chee SHIU, Zeng Min Song

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

A set S of vertices of the graph G is called k-reducible if the following is true: G is k-choosable if and only if G-S is k-choosable. A k-reduced subgraph H of G is a subgraph of G such that H contains no k-reducible set of some specific forms. In this paper, we show that a 3-reduced subgraph of a non-3-choosable plane graph G contains either adjacent 5-faces, or an adjacent 4-face and k-face, where k≤6. Using this result, we obtain some sufficient conditions for a plane graph to be 3-choosable. In particular, if G is of girth 4 and contains no 5- and 6-cycles, then G is 3-choosable.

Original languageEnglish
Pages (from-to)297-301
Number of pages5
JournalDiscrete Mathematics
Volume294
Issue number3
DOIs
Publication statusPublished - 6 May 2005

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Choosability
  • Plane graph
  • Reduced subgraph

Fingerprint

Dive into the research topics of 'The 3-choosability of plane graphs of girth 4'. Together they form a unique fingerprint.

Cite this