Partitioning random graphs into monochromatic components

Deepak Bal, Louis DeBiasio

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

Erdős, Gyàrfàs, and Pyber (1991) conjectured that every r-colored complete graph can be partitioned into at most r – 1 monochromatic components; this is a strengthening of a conjecture of Lovàsz (1975) and Ryser (1970) in which the components are only required to form a cover. An important partial result of Haxell and Kohayakawa (1995) shows that a partition into r monochromatic components is possible for sufficiently large r-colored complete graphs. We start by extending Haxell and Kohayakawa’s result to graphs with large minimum degree, then we provide some partial analogs of their result for random graphs. In particular, we show that if (formula presented), then a.a.s. in every 2- coloring of G(n; p) there exists a partition into two monochromatic components, and for r ≥ 2 if p << (formula presented), then a.a.s. there exists an r-coloring of G(n, p) such that there does not exist a cover with a bounded number of components. Finally, we consider a random graph version of a classic result of Gyàrfàs (1977) about large monochromatic components in r-colored complete graphs. We show that if p = ω(1)/n, then a.a.s. in every r-coloring of G(n, p) there exists a monochromatic component of order at least (formula presented).

Original languageEnglish
Article number#P1.18
JournalElectronic Journal of Combinatorics
Volume24
Issue number1
StatePublished - 3 Feb 2017

Fingerprint

Coloring
Random Graphs
Partitioning
Colored Graph
Complete Graph
Colouring
Partition
Cover
Partial
Number of Components
Minimum Degree
Strengthening
Analogue
Graph in graph theory

Cite this

@article{7da0947fd2184acd842b6abf2de17f56,
title = "Partitioning random graphs into monochromatic components",
abstract = "Erdős, Gy{\`a}rf{\`a}s, and Pyber (1991) conjectured that every r-colored complete graph can be partitioned into at most r – 1 monochromatic components; this is a strengthening of a conjecture of Lov{\`a}sz (1975) and Ryser (1970) in which the components are only required to form a cover. An important partial result of Haxell and Kohayakawa (1995) shows that a partition into r monochromatic components is possible for sufficiently large r-colored complete graphs. We start by extending Haxell and Kohayakawa’s result to graphs with large minimum degree, then we provide some partial analogs of their result for random graphs. In particular, we show that if (formula presented), then a.a.s. in every 2- coloring of G(n; p) there exists a partition into two monochromatic components, and for r ≥ 2 if p << (formula presented), then a.a.s. there exists an r-coloring of G(n, p) such that there does not exist a cover with a bounded number of components. Finally, we consider a random graph version of a classic result of Gy{\`a}rf{\`a}s (1977) about large monochromatic components in r-colored complete graphs. We show that if p = ω(1)/n, then a.a.s. in every r-coloring of G(n, p) there exists a monochromatic component of order at least (formula presented).",
author = "Deepak Bal and Louis DeBiasio",
year = "2017",
month = "2",
day = "3",
language = "English",
volume = "24",
journal = "Electronic Journal of Combinatorics",
issn = "1077-8926",
publisher = "Electronic Journal of Combinatorics",
number = "1",

}

Partitioning random graphs into monochromatic components. / Bal, Deepak; DeBiasio, Louis.

In: Electronic Journal of Combinatorics, Vol. 24, No. 1, #P1.18, 03.02.2017.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Partitioning random graphs into monochromatic components

AU - Bal, Deepak

AU - DeBiasio, Louis

PY - 2017/2/3

Y1 - 2017/2/3

N2 - Erdős, Gyàrfàs, and Pyber (1991) conjectured that every r-colored complete graph can be partitioned into at most r – 1 monochromatic components; this is a strengthening of a conjecture of Lovàsz (1975) and Ryser (1970) in which the components are only required to form a cover. An important partial result of Haxell and Kohayakawa (1995) shows that a partition into r monochromatic components is possible for sufficiently large r-colored complete graphs. We start by extending Haxell and Kohayakawa’s result to graphs with large minimum degree, then we provide some partial analogs of their result for random graphs. In particular, we show that if (formula presented), then a.a.s. in every 2- coloring of G(n; p) there exists a partition into two monochromatic components, and for r ≥ 2 if p << (formula presented), then a.a.s. there exists an r-coloring of G(n, p) such that there does not exist a cover with a bounded number of components. Finally, we consider a random graph version of a classic result of Gyàrfàs (1977) about large monochromatic components in r-colored complete graphs. We show that if p = ω(1)/n, then a.a.s. in every r-coloring of G(n, p) there exists a monochromatic component of order at least (formula presented).

AB - Erdős, Gyàrfàs, and Pyber (1991) conjectured that every r-colored complete graph can be partitioned into at most r – 1 monochromatic components; this is a strengthening of a conjecture of Lovàsz (1975) and Ryser (1970) in which the components are only required to form a cover. An important partial result of Haxell and Kohayakawa (1995) shows that a partition into r monochromatic components is possible for sufficiently large r-colored complete graphs. We start by extending Haxell and Kohayakawa’s result to graphs with large minimum degree, then we provide some partial analogs of their result for random graphs. In particular, we show that if (formula presented), then a.a.s. in every 2- coloring of G(n; p) there exists a partition into two monochromatic components, and for r ≥ 2 if p << (formula presented), then a.a.s. there exists an r-coloring of G(n, p) such that there does not exist a cover with a bounded number of components. Finally, we consider a random graph version of a classic result of Gyàrfàs (1977) about large monochromatic components in r-colored complete graphs. We show that if p = ω(1)/n, then a.a.s. in every r-coloring of G(n, p) there exists a monochromatic component of order at least (formula presented).

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

M3 - Article

AN - SCOPUS:85011607417

VL - 24

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

SN - 1077-8926

IS - 1

M1 - #P1.18

ER -