A generalization of the Erdos-Ko-Rado theorem

被引：1

作者：

Alishahi, Meysam ^{[1
]}

Hajiabolhassan, Hossein ^{[1
]}

Taherkhani, Ali ^{[1
]}

机构：

[1] Shaheed Beheshti Univ, Dept Math Sci, GC, Tehran, Iran

来源：

DISCRETE MATHEMATICS | 2010年 / 310卷 / 01期

关键词：

Erdos-Ko-Rado theorem; Graph homomorphism; Local chromatic number; LOCAL CHROMATIC NUMBER; COLORINGS; GRAPHS;

D O I：

10.1016/j.disc.2009.07.020

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this note, we investigate some properties of local Kneser graphs defined in [Janos Korner, Concetta Pilotto, Gabor Simonyi, Local chromatic number and sperner capacity, J. Combin. Theory Ser. B 95 (1) (2005) 101-117]. In this regard, as a generalization of the Erdos-Ko-Rado theorem, we characterize the maximum independent sets of local Kneser graphs. Next, we provide an upper bound for their chromatic number. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：188 / 191

页数：4

共 12 条

[1] HOMOMORPHISMS OF 3-CHROMATIC GRAPHS
ALBERTSON, MO
COLLINS, KL
[J]. DISCRETE MATHEMATICS, 1985, 54 (02) : 127 - 132
[2] Locally restricted colorings
Blöchliger, I
de Werra, D
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (01) : 158 - 165
[3] A NOTE ON THE STAR CHROMATIC NUMBER
BONDY, JA
HELL, P
[J]. JOURNAL OF GRAPH THEORY, 1990, 14 (04) : 479 - 482
[4] COLORING GRAPHS WITH LOCALLY FEW COLORS
ERDOS, P
FUREDI, Z
HAJNAL, A
KOMJATH, P
RODL, V
SERESS, A
[J]. DISCRETE MATHEMATICS, 1986, 59 (1-2) : 21 - 34
[5] INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
ERDOS, P
RADO, R
KO, C
[J]. QUARTERLY JOURNAL OF MATHEMATICS, 1961, 12 (48) : 313 - &
[6] Hell P., 2004, OXFORD LECT SERIES M, V28
[7] Kneser M., 1955, Jahresber. Dtsch. Math. her., V58, P27
[8] Local chromatic number and Sperner capacity
Körner, J
Pilotto, C
Simonyi, G
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 95 (01) : 101 - 117
[9] KNESER CONJECTURE, CHROMATIC NUMBER, AND HOMOTOPY
LOVASZ, L
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1978, 25 (03) : 319 - 324
[10] MOHAR B, 2009, LOCAL CHROMATI UNPUB

← 1 2 →