An analogue of Hajós' theorem for the circular chromatic number. II (Q1409583): Difference between revisions
From MaRDI portal
m rollbackEdits.php mass rollback Tag: Rollback |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00373-002-0505-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2020733172 / rank | |||
Normal rank |
Latest revision as of 18:42, 21 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An analogue of Hajós' theorem for the circular chromatic number. II |
scientific article |
Statements
An analogue of Hajós' theorem for the circular chromatic number. II (English)
0 references
16 October 2003
0 references
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.
0 references
circular chromatic number
0 references
Hajos' Theorem
0 references