Construction of K n-minor free graphs with given circular chromatic number

Sheng Chyang Liaw, Zhishi Pan, Xuding Zhu

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

For each integer n5 and each rational number r in the interval [2,n-1], we construct a K n-minor free graph G with χ c(G)=r. This answers a question asked by Zhu (Discrete Mathematics, 229 (1-3) (2001) 371). In case n=5, the constructed graphs are actually planar. Such planar graphs were first constructed in J. Graph Theory 24 (1997) 33 (for ∈[2,3]) and in J. Combin. Theory 76 (1999) 170 (for r∈[3,4]). However, our construction and proof are much simpler.

Original languageEnglish
Pages (from-to)191-206
Number of pages16
JournalDiscrete Mathematics
Volume263
Issue number1-3
DOIs
StatePublished - 28 Feb 2003

Keywords

  • Circular chromatic number
  • Hadwiger conjecture
  • K -minor free graphs
  • Planar graphs
  • Series-parallel construction

Fingerprint

Dive into the research topics of 'Construction of K n-minor free graphs with given circular chromatic number'. Together they form a unique fingerprint.

Cite this