Equitable coloring of Kneser graphs

Robert Fidytek; Hanna Furmańczyk; Paweł Żyliński

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 1, page 119-142
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Robert Fidytek, Hanna Furmańczyk, and Paweł Żyliński. "Equitable coloring of Kneser graphs." Discussiones Mathematicae Graph Theory 29.1 (2009): 119-142. <http://eudml.org/doc/270528>.

@article{RobertFidytek2009,
abstract = {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.},
author = {Robert Fidytek, Hanna Furmańczyk, Paweł Żyliński},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {equitable coloring; Kneser graph},
language = {eng},
number = {1},
pages = {119-142},
title = {Equitable coloring of Kneser graphs},
url = {http://eudml.org/doc/270528},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Robert Fidytek
AU - Hanna Furmańczyk
AU - Paweł Żyliński
TI - Equitable coloring of Kneser graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 1
SP - 119
EP - 142
AB - 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.
LA - eng
KW - equitable coloring; Kneser graph
UR - http://eudml.org/doc/270528
ER -

References

top
  1. [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. Zbl0168.26205
  2. [2] H. Furmańczyk, Equitable coloring of graphs, in: Graph Colorings, ed. M. Kubale, Contemporary Mathematics 352, AMS, Ann Arbor (2004) 35-53. 
  3. [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. Zbl1025.05026
  4. [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 Zbl0884.05041
  5. [5] M. Kneser, Aufgabe 360, Jahresbericht der Deutschen Mathematiker-Vereinigung 2, Abteilung 58 (1955), pp. 27. 
  6. [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. Zbl0996.05049
  7. [7] Z. Lonc, Decompositions of hypergraphs into hyperstars, Discrete Math. 66 (1987) 157-168, doi: 10.1016/0012-365X(87)90128-2. Zbl0651.05051
  8. [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. Zbl0418.05028
  9. [9] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973) 920-922, doi: 10.2307/2319405. Zbl0279.05106
  10. [10] A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch Wiskd. III Ser 26 (1978) 454-461. Zbl0432.05026
  11. [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. Zbl0293.05115
  12. [12] S. Stahl, The multichromatic numbers of some Kneser graphs, Discrete Math. 185 (1998) 287-291, doi: 10.1016/S0012-365X(97)00211-2. Zbl0956.05045
  13. [13] A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551-559, doi: 10.1002/jgt.3190120411. Zbl0658.05028

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.