Highly connected monochromatic subgraphs of two-colored complete graphs

被引：2

作者：

Luczak, Tomasz ^{[1
,2
]}

机构：

[1] Adam Mickiewicz Univ, Fac Math & CS, PL-61614 Poznan, Poland

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

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2016年 / 117卷

关键词：

Connectivity; Monochromatic subgraph; Colorings; MULTICOLORED GRAPHS;

D O I：

10.1016/j.jctb.2015.11.006

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that each 2-edge coloring of the complete graph on n vertices leads to a monochromatic k-connected subgraph on at least n - 2(k - 1) vertices, provided n >= 4k - 3. It settles in the affirmative a conjecture of Bollobas and Gyarfas. (C) 2015 Elsevier Inc. All rights reserved.

引用

页码：88 / 92

页数：5

共 5 条

[1] Highly connected monochromatic subgraphs [J].