×

Planar graphs with circular chromatic numbers between 3 and 4. (English) Zbl 0933.05053

This paper proves that for every rational number \(r\) between 3 and 4, there exists a planar graph \(G\) whose circular chromatic number is equal to \(r\). Combining this result with a recent result of Moser, we arrive at the conclusion that every rational number \(r\) between 2 and 4 is the circular chromatic number of a planar graph. \(\copyright\) Academic Press.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J. A.; Hell, P., A note on the star chromatic number, J. Graph Theory, 14, 479-482 (1990) · Zbl 0706.05022
[2] G. J. Chang, L. Huang, and, X. Zhu, Circular chromatic numbers of Mycielski’s graphs, Discrete Math, in press.; G. J. Chang, L. Huang, and, X. Zhu, Circular chromatic numbers of Mycielski’s graphs, Discrete Math, in press. · Zbl 0941.05026
[3] G. J. Chang, L. Huang, and, X. Zhu, The circular chromatic number and the fractional chromatic number of distance graphs, European J. Comb, in press.; G. J. Chang, L. Huang, and, X. Zhu, The circular chromatic number and the fractional chromatic number of distance graphs, European J. Comb, in press. · Zbl 0905.05032
[4] C. Chien, and, X. Zhu, The circular chromatic numbers of series-parallel graphs of large girth, preprint, 1999.; C. Chien, and, X. Zhu, The circular chromatic numbers of series-parallel graphs of large girth, preprint, 1999.
[5] Diestel, R., Graph Theory (1997), Springer-Verlag: Springer-Verlag New York
[6] Guichard, D. R., Acyclic graph colouring and the complexity of the star chromatic number, J. Graph Theory, 17, 129-134 (1993) · Zbl 0830.05031
[7] P. Hell, and, X. Zhu, The circular chromatic numbers of series-parallel graphs, J. Graph Theory, in press.; P. Hell, and, X. Zhu, The circular chromatic numbers of series-parallel graphs, J. Graph Theory, in press. · Zbl 0944.05037
[8] Goddyn, L. A.; Tarsi, M.; Zhang, C. Q., On \((k, d)\)-colourings and fractional nowhere-zero flows, J. Graph Theory, 28, 155-161 (1998) · Zbl 0922.05027
[9] L. A. Goddyn, personal communication, 1997.; L. A. Goddyn, personal communication, 1997.
[10] Moser, D., The star-chromatic number of planar graphs, J. Graph Theory, 24, 33-43 (1997) · Zbl 0870.05017
[11] Niven, I., An Introduction to the Theory of Numbers (1991), Wiley: Wiley New York
[12] E. Steffen, personal communication, 1997, 1998.; E. Steffen, personal communication, 1997, 1998.
[13] Steffen, E.; Zhu, X., On the star chromatic numbers of graphs, Combinatorica, 16, 439-448 (1996) · Zbl 0860.05036
[14] Vince, A., Star chromatic number, J. Graph Theory, 12, 551-559 (1988) · Zbl 0658.05028
[15] Zhu, X., Graphs whose circular chromatic number equal the chromatic number, Combinatorica, 19, 139-149 (1999) · Zbl 0929.05025
[16] Zhu, X., Star chromatic numbers and product of graphs, J. Graph Theory, 16, 557-569 (1992) · Zbl 0766.05033
[17] Zhu, X., A simple proof of Moser’s Theorem, J. Graph Theory, 30, 19-26 (1999) · Zbl 0929.05033
[18] Zhu, X., Construction of uniquely \(H\)-colorable graphs, J. Graph Theory, 30, 1-6 (1999) · Zbl 0937.05043
[19] X. Zhu, Circular colouring and graph minors, preprint, 1997.; X. Zhu, Circular colouring and graph minors, preprint, 1997.
[20] Zhu, X., Circular coloring and graph homomorphism, Bull. Austral. Math. Soc., 59, 83-97 (1999) · Zbl 0923.05025
[21] X. Zhu, The circular chromatic number, a survey, preprint, 1997.; X. Zhu, The circular chromatic number, a survey, preprint, 1997.
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.