Construction of \(K_{n}\)-minor free graphs with given circular chromatic number
type: Item
instance of: scholarly article
title: Construction of \(K_{n}\)-minor free graphs with given circular chromatic number
zbMATH Open document ID: 1011.05060
DOI: 10.1016/S0012-365X(02)00529-0
author: Sheng-Chyang Liaw
author: Zhishi Pan
author: Xuding Zhu
published in: Discrete Mathematics
publication date: 2003-04-09T00:00:00Z
review text: In this paper it is shown that for each integer \(n\geq 5\) and each rational number \(r\) in the interval \([2,n-1]\), there is a \(K_{n}\)-minor free graph \(G\) with \(\chi_{c}(G)=r\), where \(\chi _{c}(G)\) denotes the circular chromatic number of \(G\). This answers a question asked by \textit{X. Zhu} [Discrete Math. 229, 371-410 (2001; Zbl 0973.05030)]. To prove this the required graphs are actually constructed, based on the labeling method of calculating \(\chi _{c}(G)\). For \(2<p/q<4\), the \(K_{5}\)-minor free graph \(H\) with \(\chi _{c}(H)=p/q\) constructed in this way is a planar graph. This produces an alternate proof of the results by \textit{D. Moser} [J. Graph Theory 24, 33-43 (1997; Zbl 0870.05017)] and \textit{X. Zhu} [J. Comb. Theory, Ser. B 76, 170-200 (1999; Zbl 0933.05053)]. The proof is based on a different idea and is simpler than the original proofs.
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1895993
zbMATH Keywords: circular chromatic number
zbMATH Keywords: \(K_{n}\)-minor free graph
zbMATH Keywords: series-parallel construction
zbMATH Keywords: planar graph
zbMATH Keywords: Hadwiger conjecture
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00529-0
OpenAlex ID: W2083271302
description: scientific article; zbMATH DE number 1895993