A note on edge-colourings avoiding rainbow K4 and monochromatic Km

被引：0

作者：

Jungic, Veselin ^{[1
]}

Kaiser, Tomas S. ^{[2
,3
]}

Kral, Daniel ^{[4
]}

机构：

[1] Simon Fraser Univ, Dept Math, Burnaby, BC V5A 2R6, Canada

[2] Univ W Bohemia, Dept Math, Plzen 30614, Czech Republic

[3] Univ W Bohemia, Inst Theoret Comp Sci, Plzen 30614, Czech Republic

[4] Charles Univ Prague, Fac Math & Phys, Inst Theoret Comp Sci ITI, Prague 11800, Czech Republic

来源：

ELECTRONIC JOURNAL OF COMBINATORICS | 2009年 / 16卷 / 01期

关键词：

ANTI-RAMSEY THEOREM; GRAPHS;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study the mixed Ramsey number max R(n, K-m, K-r),defined as the maximum number of colours in an edge-colouring of the complete graph K-n, such that K-n has no monochromatic complete subgraph on m vertices and no rainbow complete subgraph on r vertices. Improving an upper bound of Axenovich and Iverson, we show that max R(n, K-m, K-4) <= n(3/2) root 2m for all m >= 3. Further, we discuss a possible way to improve their lower bound on max R(n, K-4, K-4) based on incidence graphs of finite projective planes.

引用

页数：9

共 16 条

[1] On a generalized anti-Ramsey problem [J].

Axenovich, M ;

Kündgen, A .

COMBINATORICA, 2001, 21 (03) :335-349

[2]

AXENOVICH M, EDGE COLORINGS UNPUB

[3]

BROWN WG, 1967, J LONDON MATH SOC, V42, P514

[4]

Cameron P.J., 1995, HDB COMBINATORICS, P647

[5]

Chowla S., 1944, Proc. Nat. Acad. Sci. India Sect. A, V14, P1

[6]

Erdos P., 1944, J LOND MATH SOC, V19, P208

[7]

ERDOS P, 1973, INFINITE FINITE SETS, V2, P633

[8]

Erds P., 1935, Comp. Math, V2, P463

[9] On pattern Ramsey numbers of graphs [J].

Jamison, RE ;

West, DB .

GRAPHS AND COMBINATORICS, 2004, 20 (03) :333-339

[10] An anti-Ramsey theorem on cycles [J].

Montellano-Ballesteros, JJ ;

Neumann-Lara, V .

GRAPHS AND COMBINATORICS, 2005, 21 (03) :343-354

← 1 2 →