Unavoidable subgraphs of colored graphs

Jonathan Cutler, Balázs Montágh

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

Abstract

A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper, we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let Sk be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint Kk / 2's or simply one Kk / 2. Bollobás conjectured that for all k and ε{lunate} > 0, there exists an n (k, ε{lunate}) such that if n ≥ n (k, ε{lunate}) then every two-edge-coloring of Kn, in which the density of each color is at least ε{lunate}, contains a member of this family. We solve this conjecture and present a series of results bounding n (k, ε{lunate}) for different ranges of ε{lunate}. In particular, if ε{lunate} is sufficiently close to frac(1, 2), the gap between our upper and lower bounds for n (k, ε{lunate}) is smaller than those for the classical Ramsey number R (k, k).

Original languageEnglish
Pages (from-to)4396-4413
Number of pages18
JournalDiscrete Mathematics
Volume308
Issue number19
DOIs
StatePublished - 6 Oct 2008

Fingerprint

Colored Graph
Edge-colored Graph
Subgraph
Color
Graph theory
Coloring
Ramsey Theory
Ramsey number
Edge Coloring
Graph in graph theory
Upper and Lower Bounds
Disjoint
Integer
Series
Range of data
Family

Keywords

  • Ramsey theory
  • Unavoidable structures

Cite this

Cutler, Jonathan ; Montágh, Balázs. / Unavoidable subgraphs of colored graphs. In: Discrete Mathematics. 2008 ; Vol. 308, No. 19. pp. 4396-4413.
@article{e24415dce88c4315b316117017c2240b,
title = "Unavoidable subgraphs of colored graphs",
abstract = "A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper, we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let Sk be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint Kk / 2's or simply one Kk / 2. Bollob{\'a}s conjectured that for all k and ε{lunate} > 0, there exists an n (k, ε{lunate}) such that if n ≥ n (k, ε{lunate}) then every two-edge-coloring of Kn, in which the density of each color is at least ε{lunate}, contains a member of this family. We solve this conjecture and present a series of results bounding n (k, ε{lunate}) for different ranges of ε{lunate}. In particular, if ε{lunate} is sufficiently close to frac(1, 2), the gap between our upper and lower bounds for n (k, ε{lunate}) is smaller than those for the classical Ramsey number R (k, k).",
keywords = "Ramsey theory, Unavoidable structures",
author = "Jonathan Cutler and Bal{\'a}zs Mont{\'a}gh",
year = "2008",
month = "10",
day = "6",
doi = "10.1016/j.disc.2007.08.102",
language = "English",
volume = "308",
pages = "4396--4413",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "19",

}

Unavoidable subgraphs of colored graphs. / Cutler, Jonathan; Montágh, Balázs.

In: Discrete Mathematics, Vol. 308, No. 19, 06.10.2008, p. 4396-4413.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Unavoidable subgraphs of colored graphs

AU - Cutler, Jonathan

AU - Montágh, Balázs

PY - 2008/10/6

Y1 - 2008/10/6

N2 - A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper, we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let Sk be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint Kk / 2's or simply one Kk / 2. Bollobás conjectured that for all k and ε{lunate} > 0, there exists an n (k, ε{lunate}) such that if n ≥ n (k, ε{lunate}) then every two-edge-coloring of Kn, in which the density of each color is at least ε{lunate}, contains a member of this family. We solve this conjecture and present a series of results bounding n (k, ε{lunate}) for different ranges of ε{lunate}. In particular, if ε{lunate} is sufficiently close to frac(1, 2), the gap between our upper and lower bounds for n (k, ε{lunate}) is smaller than those for the classical Ramsey number R (k, k).

AB - A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper, we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let Sk be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint Kk / 2's or simply one Kk / 2. Bollobás conjectured that for all k and ε{lunate} > 0, there exists an n (k, ε{lunate}) such that if n ≥ n (k, ε{lunate}) then every two-edge-coloring of Kn, in which the density of each color is at least ε{lunate}, contains a member of this family. We solve this conjecture and present a series of results bounding n (k, ε{lunate}) for different ranges of ε{lunate}. In particular, if ε{lunate} is sufficiently close to frac(1, 2), the gap between our upper and lower bounds for n (k, ε{lunate}) is smaller than those for the classical Ramsey number R (k, k).

KW - Ramsey theory

KW - Unavoidable structures

UR - http://www.scopus.com/inward/record.url?scp=46149101586&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2007.08.102

DO - 10.1016/j.disc.2007.08.102

M3 - Article

VL - 308

SP - 4396

EP - 4413

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 19

ER -