An analogue of Hajós' theorem for the circular chromatic number. II
type: Item
instance of: scholarly article
title: An analogue of Hajós' theorem for the circular chromatic number. II
zbMATH Open document ID: 1030.05042
author: Xuding Zhu
published in: Graphs and Combinatorics
publication date: 2003-10-16T00:00:00Z
review text: For a graph \(G=\left( V,E\right) \) an \(r\)-colouring \(f\) of \(G\) is a mapping \(f:V\rightarrow [0,r)\) such that \(1\leq \left|f\left( x\right) -f\left( y\right) \right|\leq r-1\) for every edge \(xy\) of \(G\). The circular chromatic number \(\chi _{c}\left( G\right) \) is the infimum of those \(r\) for which \(G\) has an \(r\)-colouring. For \(k\geq 2d\) the circular complete graph \(K_{k/d}\) is the graph with vertex set \(\{0,1,\ldots, k-1\}\) in which \(i\) is adjacent to \(j\) if and only if \(d\leq \left|i-j\right|\leq k-d\). In a previous paper [Proc. Am. Math. Soc. 129, 2845-2852 (2001; Zbl 0971.05042)] the author designed a set of graph operations and showed that, for \(\frac{k}{d}\geq 3,\) all graphs with \(\chi _{c}(G)\geq \frac{k}{d}\) can be constructed from copies of the graph \(K_{k/d}\) by repeatedly applying these operations. In this paper he designs a set of graph operations to prove a similar result for the case \(2\leq \frac{k}{d}<3.\) The combination of these results is a complete analogue of Hajos' theorem (which states that every graph with chromatic number at least \(k\) can be constructed from copies of \(K_{k}\) by repeatedly applying three operations: adding vertices and edges, identifying nonadjacent vertices and applying Hajos' sum) for the circular chromatic number.
reviewed by: Marietjie Frick
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1993521
zbMATH Keywords: circular chromatic number
zbMATH Keywords: Hajos' Theorem
MaRDI profile type: Publication
full work available at URL: s00373-002-0505-9
OpenAlex ID: W2020733172
DOI: 10.1007/S00373-002-0505-9
Recommended article: An analogue of Hajós' theorem for the circular chromatic number
Recommended article: Hajós theorem for colorings of edge-weighted graphs
Recommended article: Q3424895
Recommended article: The circular chromatic number of induced subgraphs
Recommended article: Q5491998
Recommended article: Chromatic numbers in some graphs
Recommended article: Graphs whose circular chromatic number equals the chromatic number
Recommended article: Circular chromatic number of subgraphs
Recommended article: Q4545983
Recommended article: Q4455327
description: scientific article; zbMATH DE number 1993521