Partitioning random graphs into monochromatic components

MaRDI QIDQ510329zbMATH OpenFDO

Authors Deepak Bal, Louis DeBiasio

Publication date 17 February 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.09168, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p18

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Ramsey theoryrandom graphsRyser's conjecture

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Ramsey theory (05D10)

Abstract: ErdH{o}s, Gy'arf'as, 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'asz (1975) 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 $pgeleft(frac27lognnight{)}^{1/3}$, then a.a.s. in every $2$-coloring of $G(n,p)$ there exists a partition into two monochromatic components, and for $rgeq2$ if $pllleft(fracrlognnight{)}^{1/r}$, 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'arf'as (1977) about large monochromatic components in $r$-colored complete graphs. We show that if $p=fracomega(1)n$, then a.a.s. in every $r$-coloring of $G(n,p)$ there exists a monochromatic component of order at least $(1-o(1))fracnr-1$.

Recommendations

• Monochromatic cycle partitions in random graphs
• Partitioning by monochromatic trees
• Monochromatic cycle covers in random graphs
• Large monochromatic components in multicolored bipartite graphs
• Bounded monochromatic components for random graphs

Cites work

• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• An improved bound for the monochromatic cycle partition number
• Calculating Ramsey numbers by partitioning colored graphs
• Coloring the edges of a random graph without a monochromatic giant component
• Combinatorial theorems relative to a random set
• Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
• Decompositions of edge-colored infinite complete graphs into monochromatic paths
• Generalizing the Ramsey problem through diameter
• Highly connected monochromatic subgraphs of multicolored graphs
• Introduction to Random Graphs
• Large monochromatic components in edge colorings of graphs: A survey
• Local connectivity of a random graph
• Maximum degree and fractional matchings in uniform hypergraphs
• Monochromatic Paths in Graphs
• Monochromatic cycle partitions of graphs with large minimum degree
• Partition of graphs and hypergraphs into monochromatic connected parts
• Partitioning 2-edge-colored graphs by monochromatic paths and cycles
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
• Partitioning by monochromatic trees
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Path Ramsey number for random graphs
• Ramsey games with giants
• Ryser's conjecture for tripartite 3-graphs
• Some Ramsey-Turán type problems and related questions
• Szemerédi's regularity Lemma for matrices and sparse graphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Threshold Functions for Ramsey Properties
• Vertex coverings by monochromatic cycles and trees

Cited in

(17)

• Large monochromatic components and long monochromatic cycles in random hypergraphs
• The power of many colours
• Covering 3-coloured random graphs with monochromatic trees
• Generalizations and strengthenings of Ryser's conjecture
• Partitioning problems via random processes
• Monochromatic partitions in local edge colorings
• Covering 3-edge-colored random graphs with monochromatic trees
• Covering graphs by monochromatic trees and Helly-type results for hypergraphs
• Coloring the edges of a random graph without a monochromatic giant component
• Vertex covering with monochromatic pieces of few colours
• Bounded monochromatic components for random graphs
• Covering random graphs with monochromatic trees
• Large monochromatic components in expansive hypergraphs
• Large monochromatic components in edge colored graphs with a minimum degree condition
• Large monochromatic components in colorings of complete hypergraphs
• Monochromatic cycle partitions in random graphs
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles

This page was built for publication: Partitioning random graphs into monochromatic components

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510329)