×

Circular chromatic number and Mycielski construction. (English) Zbl 1030.05047

There is given another sufficient condition for a graph to have its circular chromatic number (also known as the star chromatic number) equal to its chromatic number. This condition is applied to the study of the circular chromatic number of Mycielski’s graphs, especially, the circular chromatic number of the iterated Mycielskian of complete graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbott, J Graph Theory 17 pp 349– (1993)
[2] Bondy, J Graph Theory 14 pp 479– (1990)
[3] Chang, Discrete Math 205 pp 23– (1999)
[4] Circular chromatic number and Mycielski graphs, manuscript, 2000.
[5] Fisher, J Graph Theory 20 pp 403– (1995)
[6] Guichard, J Graph Theory 17 pp 129– (1993)
[7] Huang, J Graph Theory 32 pp 63– (1999)
[8] Larsen, J Graph Theory 19 pp 411– (1995)
[9] and Acyclic orientations and the circular chromatic number of a graph, manuscript.
[10] Mycielski, Colloq Math 3 pp 161– (1955)
[11] Steffen, Combinatorica 16 pp 439– (1996)
[12] Vince, J Graph Theory 12 pp 551– (1988)
[13] Zhu, J Graph Theory 16 pp 557– (1992)
[14] Zhu, J Graph Theory 23 pp 33– (1996)
[15] Zhu, Combinatorica 19 pp 139– (1999)
[16] Zhu, a survey, Discrete Math 229 pp 371– (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.