TY - JOUR

T1 - Partitioning random graphs into monochromatic components

AU - Bal, Deepak

AU - DeBiasio, Louis

N1 - Publisher Copyright:
© 2017, Australian National University. All Rights Reserved.

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

U2 - 10.37236/6089

DO - 10.37236/6089

M3 - Article

AN - SCOPUS:85011607417

SN - 1077-8926

VL - 24

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - #P1.18

ER -