Partitioning random graphs into monochromatic components

zbMATH Open1355.05192arXiv1509.09168MaRDI QIDQ510329FDOQ510329

Authors: Deepak Bal, Louis DeBiasio 

Publication date: 17 February 2017

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

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$.

Full work available at URL: https://arxiv.org/abs/1509.09168

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

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

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)

Cites Work

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

Cited In (18)

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

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)