PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2009 | 29 | 1 | 119-142
Tytuł artykułu

Equitable coloring of Kneser graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
29
Numer
1
Strony
119-142
Opis fizyczny
Daty
wydano
2009
otrzymano
2007-12-07
poprawiono
2008-05-09
zaakceptowano
2008-05-09
Twórcy
  • University of Gdańsk, Institute of Computer Science, 80-952 Gdańsk, Poland
  • University of Gdańsk, Institute of Computer Science, 80-952 Gdańsk, Poland
  • University of Gdańsk, Institute of Computer Science, 80-952 Gdańsk, Poland
Bibliografia
  • [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.
  • [2] H. Furmańczyk, Equitable coloring of graphs, in: Graph Colorings, ed. M. Kubale, Contemporary Mathematics 352, AMS, Ann Arbor (2004) 35-53.
  • [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.
  • [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
  • [5] M. Kneser, Aufgabe 360, Jahresbericht der Deutschen Mathematiker-Vereinigung 2, Abteilung 58 (1955), pp. 27.
  • [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.
  • [7] Z. Lonc, Decompositions of hypergraphs into hyperstars, Discrete Math. 66 (1987) 157-168, doi: 10.1016/0012-365X(87)90128-2.
  • [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.
  • [9] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973) 920-922, doi: 10.2307/2319405.
  • [10] A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch Wiskd. III Ser 26 (1978) 454-461.
  • [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.
  • [12] S. Stahl, The multichromatic numbers of some Kneser graphs, Discrete Math. 185 (1998) 287-291, doi: 10.1016/S0012-365X(97)00211-2.
  • [13] A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551-559, doi: 10.1002/jgt.3190120411.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1436
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.