 Забыли?

?

139

код для вставкиСкачать
```Note on the n t h
Chromatic Numbers of
the Grotzsch Graph*
-
Saul StahI
DEPARTMENT OF MATHEMATICS
UNiVERSlTY OF KANSAS
LA WKENCE, KANSAS 66045
e-mai1:stahlQkuhub. cc. ukans.edu
ABSTRACT
It is shown that the n t h chromatic numbers of the Grotzsch graph provide the answer
to an issue raised by Hilton, Rado, and Scott (Nanta Math. 9 (19761, 152-1 55). 0 1996
John Wiley & Sons, Inc.
1. INTRODUCTION
For any nonnegative integer n, the nth chromatic number of the graph G, denoted by ,yrl(G),
is the least number of colors required for the purpose of coloring each of the vertices of G
with a set of n colors so that adjacent vertices receive disjoint sets of colors. It follows from
16, Theorem 1 1 land [4, Proposition 31 that for each graph G there exist nonnegative integers
no(G) and n’(G) such that
It is well known  that for the Grotzsch graph G, of Figure 1 , ,yl(G,)
it follows from [ I , 31 that no(G,) = 10 and ,ylo(G,) = 29. Thus,
xn+io(Gr)
= ,yn(G,) + 29
However, Table I demonstrates that
,yll(G,) 9
for all
=
,y(G,)
=
4 and
n e n’(G,)
32 so that
*This research was done while the author was being partially supported by National Science
Foundation Grant DMS-9203455.
Journal of Graph Theory, Vol. 21, No. 2, 207-209 (1996)
0 1996 John Wiley & Sons, Inc.
CCC 0364-9024/96/020207-03
208 JOURNAL OF GRAPH THEORY
X
X
4
FIGURE 1
and hence n’(G,) > 1.
This is the only known example of a graph for which n’(G) # 0 (see the concluding remark
of ). Moreover, it is easily computed that x ~ ( G , )= 6 and x?(G,.) = 9. Using the facts that
,y,((G,) 2 29n/10 for all n [ l , 31 and that x,~(G)is subadditive in the variable n, it is not
difficult to show that in fact ,yI1(G,)= [29n/10] for n 2 2 and hence n’(G,) = 2.
The proof of the existence of n’(G) is nonconstructive and it would be interesting to obtain
an upper bound for it.
ACKNOWLEDGMENT
The author is indebted to David C. Fisher and the referees for simplifying his original argument.
TABLE I.
i = I
1 , 2, 6, 7.
x i 1 1 , 12, 16, 17,
21, 22, 26
1 , 2, 6. 7,
y i 11, 12, 28, 29,
30, 31, 32
Z
i = 2
i=3
i = 4
i=5
4, 5, 9, 10,
14, 15, 19, 20,
24. 25, 27
2, 3. 7, 8.
12, 13, 17, 18,
22, 23, 26
1. 5, 6. 10,
11, 15, 16, 20,
21, 25, 28
3. 4, 8, 9,
13, 14, 18, 19,
23, 24. 27
4, 5, 9. 10.
14, 15, 28, 29,
30, 31, 32
2, 3, 7, 8,
12, 13, 23, 29,
30, 31, 32
1 , 5, 6. 10.
1 1 , 15, 28, 29,
30, 31, 32
3, 4, 8, 9.
13, 14, 23, 29,
30, 31, 32
16, 17, 18, 19, 20, 21, 22, 24, 25. 26. 27
CHROMATIC NUMBERS OF GROTZSCH GRAPHS 209
References
[ 11 D. C. Fisher, Fractional colorings with large denominators, J. Graph Theory, to appear.
 A. J. W. Hilton, R. Rado, and S. H. Scott, Multicolouring graphs and hypergraphs, Nantu
Math. 9 (1976), 152-155.
131 M. Larsen, J. Propp, and D. Ullman, The fractional chromatic number of Mycielski’s
graphs, J . Graph Theory, 19 ( 1 995), 41 1-41 6.
 L. Lovisz, Minimax Theorems for Hypergraphs, Lecture Notes in Mathematics No. 41 1
(eds. A. Dold and B. Eckman), Springer Verlag, Berlin (1974).
[ 5 ] J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955), 161 -162.
 S. Stahl, n-Tuple colorings and associated graphs, J. Combin. Theory. Ser B 20 (1976),
185 -203.