On a generalized anti-Ramsey problem

被引:11
作者
Axenovich, M [1 ]
Kündgen, A [1 ]
机构
[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA
关键词
D O I
10.1007/s004930100000
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For positive integers p, q(1), q(2), a coloring of E(K-n) is called a (p, q(1), q(2))-coloring if the edges of every K-p receive at least q(1) and at most q(2) colors. Let R(n, p, q(1), q(2)) denote the maximum number of colors in a (p,q(1),q(2))-coloring of K-n. Given (p,q(1)) we determine the largest q(2) such that all (p,q(1),q(2))-colorings of E(K-n) have at most O(n) colors and we determine R(n,p,q(1),q(2)) asymptotically when it is of order equal to n(2). We give several bounds and constructions.
引用
收藏
页码:335 / 349
页数:15
相关论文
共 15 条
[1]  
AHLSWEDE R, 1992, J COMBIN INFORM SYST, V17, P203
[2]  
[Anonymous], P LOND MATH SOC
[3]   On generalized Ramsey theory:: The bipartite case [J].
Axenovich, M ;
Füredi, Z ;
Mubayi, D .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 79 (01) :66-86
[4]   EDGE-COLORED COMPLETE GRAPHS WITH PRECISELY COLORED SUBGRAPHS [J].
CHUNG, FRK ;
GRAHAM, RL .
COMBINATORICA, 1983, 3 (3-4) :315-324
[5]   A variant of the classical Ramsey problem [J].
Erdos, P ;
Gyarfas, A .
COMBINATORICA, 1997, 17 (04) :459-467
[6]   ON THE STRUCTURE OF LINEAR GRAPHS [J].
ERDOS, P ;
STONE, AH .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) :1087-1091
[7]  
Erdos P., 1938, MITT FORSCHUNGSINST, V2, P74
[8]  
Erdos P., 1973, ANTIRAMSEY THEOREMS
[9]  
Erdos P., 1981, Eur. J. Comb, V32, P49
[10]  
Erdos P., 1966, Studia Scientiarum Mathematicarum Hungarica, V1, P51