An analogue of Hajós’ Theorem for the circular chromatic number
HTML articles powered by AMS MathViewer
- by Xuding Zhu PDF
- Proc. Amer. Math. Soc. 129 (2001), 2845-2852 Request permission
Abstract:
This paper designs a set of graph operations and proves that starting from $G^k_d$, by repeatedly applying these operations, one can construct all graphs $G$ with $\chi _c(G) \geq k/d$ (for $k/d \geq 3$). This can be viewed as an analogue of Hajós’ Theorem for the circular chromatic number.References
- H. L. Abbott and B. Zhou, The star chromatic number of a graph, J. Graph Theory 17 (1993), no. 3, 349–360. MR 1220995, DOI 10.1002/jgt.3190170309
- J. A. Bondy and Pavol Hell, A note on the star chromatic number, J. Graph Theory 14 (1990), no. 4, 479–482. MR 1067243, DOI 10.1002/jgt.3190140412
- S. Brandt, On the structure of dense triangle-free graphs, Fachbereich Mathematik und Informatik, Series A Mathematik, Preprint No. A 97-16. (English summary)
- David R. Guichard, Acyclic graph coloring and the complexity of the star chromatic number, J. Graph Theory 17 (1993), no. 2, 129–134. MR 1217388, DOI 10.1002/jgt.3190170202
- G. Hajós, Über eine Konstruktion nicht $n$-färbbarer Graphen, Wiss. Zeitschrift Univ. Halle, Math.-Nat. 10 (1961), 113-114.
- Ryan B. Hayward, Weakly triangulated graphs, J. Combin. Theory Ser. B 39 (1985), no. 3, 200–208. MR 815392, DOI 10.1016/0095-8956(85)90050-4
- David Moser, The star-chromatic number of planar graphs, J. Graph Theory 24 (1997), no. 1, 33–43. MR 1422563, DOI 10.1002/(SICI)1097-0118(199701)24:1<33::AID-JGT5>3.0.CO;2-K
- Jaroslav Ne et il, The homomorphism structure of classes of graphs, Combin. Probab. Comput. 8 (1999), no. 1-2, 177–184. Recent trends in combinatorics (Mátraháza, 1995). MR 1684628, DOI 10.1017/S0963548398003460
- János Pach, Graphs whose every independent set has a common neighbour, Discrete Math. 37 (1981), no. 2-3, 217–228. MR 676427, DOI 10.1016/0012-365X(81)90221-1
- Eckhard Steffen and Xuding Zhu, Star chromatic numbers of graphs, Combinatorica 16 (1996), no. 3, 439–448. MR 1417353, DOI 10.1007/BF01261328
- A. Vince, Star chromatic number, J. Graph Theory 12 (1988), no. 4, 551–559. MR 968751, DOI 10.1002/jgt.3190120411
- Xu Ding Zhu, Star chromatic numbers and products of graphs, J. Graph Theory 16 (1992), no. 6, 557–569. MR 1189048, DOI 10.1002/jgt.3190160604
- Xuding Zhu, Uniquely $H$-colorable graphs with large girth, J. Graph Theory 23 (1996), no. 1, 33–41. MR 1402136, DOI 10.1002/(SICI)1097-0118(199609)23:1<33::AID-JGT3>3.3.CO;2-P
- Xuding Zhu, Graphs whose circular chromatic number equals the chromatic number, Combinatorica 19 (1999), no. 1, 139–149. MR 1722215, DOI 10.1007/s004930050050
- Xuding Zhu, A simple proof of Moser’s theorem, J. Graph Theory 30 (1999), no. 1, 19–26. MR 1658550, DOI 10.1002/(SICI)1097-0118(199901)30:1<19::AID-JGT3>3.3.CO;2-O
- Xuding Zhu, Planar graphs with circular chromatic numbers between $3$ and $4$, J. Combin. Theory Ser. B 76 (1999), no. 2, 170–200. MR 1699187, DOI 10.1006/jctb.1999.1900
- X. Zhu, Circular chromatic number, a survey, Discrete Mathematics, to appear.
- X. Zhu, Circular perfect graphs, manuscript, 1999.
- X. Zhu, Hajós’ theorem for the circular chromatic number (II), in preparation.
Additional Information
- Xuding Zhu
- Affiliation: Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 80424
- Email: zhu@math.nsysu.edu.tw
- Received by editor(s): November 16, 1999
- Received by editor(s) in revised form: February 21, 2000
- Published electronically: March 29, 2001
- Additional Notes: This research was partially supported by the National Science Council under grant NSC 89-2115-M-110-003
- Communicated by: John R. Stembridge
- © Copyright 2001 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 129 (2001), 2845-2852
- MSC (2000): Primary 05C15
- DOI: https://doi.org/10.1090/S0002-9939-01-05908-1
- MathSciNet review: 1840086