Partitioning two-coloured complete graphs into two monochromatic cycles

被引：53

作者：

Luczak, T ^{[1
]}

Rödl, V

Szemerédi, E

机构：

[1] Adam Mickiewicz Univ, Dept Discrete Math, PL-61712 Poznan, Poland

[2] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 USA

[3] Rutgers State Univ, Dept Comp Sci, New Brunswick, NJ 08903 USA

来源：

COMBINATORICS PROBABILITY & COMPUTING | 1998年 / 7卷 / 04期

关键词：

D O I：

10.1017/S0963548398003599

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that there exists n(0), such that, for every n greater than or equal to n(0) and every 2-colouring of the edges of the complete graph K-n, one can find two vertex-disjoint monochromatic cycles of different colours which cover all vertices of K-n.

引用

页码：423 / 436

页数：14

共 7 条

[1]

Ayel J., 1979, THESIS U GRENOBLE

[2]

ERDOS P, 1991, J COMB THEORY B, V51, P90, DOI 10.1016/0095-8956(91)90007-7

[3] VERTEX COVERINGS BY MONOCHROMATIC PATHS AND CYCLES [J].

GYARFAS, A .

JOURNAL OF GRAPH THEORY, 1983, 7 (01) :131-135

[4]

GYARFAS A, 1989, ALGORITHMS COMBINATO, V8, P81

[5] Partitioning complete bipartite graphs by monochromatic cycles [J].

Haxell, PE .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 69 (02) :210-218

[6] Blow-up Lemma [J].

Komlos, J ;

Sarkozy, GN ;

Szemeredi, E .

COMBINATORICA, 1997, 17 (01) :109-123

[7]

Szemeredi Endre, 1978, Problemes combinatoires et theorie des graphes, V260, P399

← 1 →