Equitable coloring of Kneser graphs
Robert Fidytek ; Hanna Furmańczyk ; Paweł Żyliński
Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 119-142 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

The Kneser graph K(n,k) is the graph whose vertices correspond to k-element subsets of set {1,2,...,n} and two vertices are adjacent if and only if they represent disjoint subsets. In this paper we study the problem of equitable coloring of Kneser graphs, namely, we establish the equitable chromatic number for graphs K(n,2) and K(n,3). In addition, for sufficiently large n, a tight upper bound on equitable chromatic number of graph K(n,k) is given. Finally, the cases of K(2k,k) and K(2k+1,k) are discussed.

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:270528 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1436,
     author = {Robert Fidytek and Hanna Furma\'nczyk and Pawe\l\ \.Zyli\'nski},
     title = {Equitable coloring of Kneser graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {29},
     year = {2009},
     pages = {119-142},
     zbl = {1181.05039},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1436}
}

Robert Fidytek; Hanna Furmańczyk; Paweł Żyliński. Equitable coloring of Kneser graphs. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 119-142. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1436/

[000] [1] A.J.W. Hilton and E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. 18 (1967) 369-384, doi: 10.1093/qmath/18.1.369. | Zbl 0168.26205

[001] [2] H. Furmańczyk, Equitable coloring of graphs, in: Graph Colorings, ed. M. Kubale, Contemporary Mathematics 352, AMS, Ann Arbor (2004) 35-53.

[002] [3] H. Hajiabolhassan and X. Zhu, Circular chromatic number of Kneser graphs, J. Combin. Theory (B) 88 (2003) 299-303, doi: 10.1016/S0095-8956(03)00032-7. | Zbl 1025.05026

[003] [4] A. Johnson, F.C. Holroyd and S. Stahl, Multichromatic numbers, star chromatic numbers and Kneser graphs, J. Graph Theory 26 (1997) 137-145, doi: 10.1002/(SICI)1097-0118(199711)26:3<137::AID-JGT4>3.0.CO;2-S | Zbl 0884.05041

[004] [5] M. Kneser, Aufgabe 360, Jahresbericht der Deutschen Mathematiker-Vereinigung 2, Abteilung 58 (1955), pp. 27.

[005] [6] K.W. Lih and D.F. Liu, Circular chromatic numbers of some reduced Kneser graphs, J. Graph Theory 41 (2002) 62-68, doi: 10.1002/jgt.10052. | Zbl 0996.05049

[006] [7] Z. Lonc, Decompositions of hypergraphs into hyperstars, Discrete Math. 66 (1987) 157-168, doi: 10.1016/0012-365X(87)90128-2. | Zbl 0651.05051

[007] [8] L. Lovasz, Kneser's conjecture, chromatic number and homotopy, J. Combin. Theory (A) 25 (1978) 319-324, doi: 10.1016/0097-3165(78)90022-5. | Zbl 0418.05028

[008] [9] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973) 920-922, doi: 10.2307/2319405. | Zbl 0279.05106

[009] [10] A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch Wiskd. III Ser 26 (1978) 454-461. | Zbl 0432.05026

[010] [11] S. Stahl, n-tuple colourings and associated graphs, J. Combin. Theory (B) 20 (1976) 185-203, doi: 10.1016/0095-8956(76)90010-1. | Zbl 0293.05115

[011] [12] S. Stahl, The multichromatic numbers of some Kneser graphs, Discrete Math. 185 (1998) 287-291, doi: 10.1016/S0012-365X(97)00211-2. | Zbl 0956.05045

[012] [13] A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551-559, doi: 10.1002/jgt.3190120411. | Zbl 0658.05028