Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

An analogue of Hajós' Theorem for the circular chromatic number


Author: Xuding Zhu
Journal: Proc. Amer. Math. Soc. 129 (2001), 2845-2852
MSC (2000): Primary 05C15
DOI: https://doi.org/10.1090/S0002-9939-01-05908-1
Published electronically: March 29, 2001
MathSciNet review: 1840086
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. H. L. Abbott and B. Zhou, The star chromatic number of a graph, J. Graph Theory 17 (1993), 349-360. MR 94g:05032
  • 2. J. A. Bondy and P. Hell, A note on the star chromatic number, J. Graph Theory 14 (1990), 479-482. MR 91i:05052
  • 3. S. Brandt, On the structure of dense triangle-free graphs, Fachbereich Mathematik und Informatik, Series A Mathematik, Preprint No. A 97-16. CMP 99:16 (English summary)
  • 4. D. R. Guichard, Acyclic graph coloring and the complexity of the star chromatic number, J. Graph Theory 17 (1993), 129-134. MR 94e:05105
  • 5. G. Hajós, Über eine Konstruktion nicht $n$-färbbarer Graphen, Wiss. Zeitschrift Univ. Halle, Math.-Nat. 10 (1961), 113-114.
  • 6. R. Hayward, Weakly triangulated graphs, J. Combin. Th. (B), 39(1985), 200-208. MR 87h:05171
  • 7. D. Moser, The star-chromatic number of planar graphs, J. Graph Theory 24(1997), 33-43. MR 97k:05082
  • 8. J. Nesetril, Homomorphism structure of classes of graphs, Combinatorics, Probability and computing 8 (1999), 177-184. MR 2000c:05068
  • 9. J. Pach, Graphs whose every independent set has a common neighbour, Discrete Math. 37(1981), 217-228. MR 84e:05094
  • 10. E. Steffen and X. Zhu, On the star chromatic numbers of graphs, Combinatorica, 16 (1996) 439-448. MR 97g:05084
  • 11. A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551-559. MR 90c:05098
  • 12. X. Zhu, Star chromatic numbers and products of graphs, J. Graph Theory 16 (1992), 557-569. MR 93i:05066
  • 13. X. Zhu, Uniquely $H$-colorable graphs with large girth, J. Graph Theory, 23 (1996), 33-41. MR 97e:05089
  • 14. X. Zhu, Graphs whose circular chromatic number equals the chromatic number, Combinatorica, 19(1)(1999), 139-149. MR 2000j:05047
  • 15. X. Zhu, A simple proof of Moser's theorem, J. Graph Theory, 30(1999), 19-26. MR 99g:05084
  • 16. X. Zhu, Planar graphs with circular chromatic numbers between $3$ and $4$, J. Combinatorial Theory (B), 76(1999), 170-200. MR 2000e:05072
  • 17. X. Zhu, Circular chromatic number, a survey, Discrete Mathematics, to appear.
  • 18. X. Zhu, Circular perfect graphs, manuscript, 1999.
  • 19. X. Zhu, Hajós' theorem for the circular chromatic number (II), in preparation.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05C15

Retrieve articles in all journals with MSC (2000): 05C15


Additional Information

Xuding Zhu
Affiliation: Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 80424
Email: zhu@math.nsysu.edu.tw

DOI: https://doi.org/10.1090/S0002-9939-01-05908-1
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
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society