Proceedings of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6826(e) ISSN 0002-9939(p)

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

Author(s): Xuding Zhu
Journal: Proc. Amer. Math. Soc. 129 (2001), 2845-2852.
MSC (2000): Primary 05C15
Posted: March 29, 2001
MathSciNet review: 1840086
Retrieve article in: PDF
This article is available free of charge

Abstract | References | Similar articles | Additional information

Abstract:

This paper designs a set of graph operations and proves that starting from , by repeatedly applying these operations, one can construct all graphs 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:

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 -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 -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 and , 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.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|