Monochromatic cycle partitions in random graphs

DOI10.1017/S0963548320000401zbMATH Open1466.05183arXiv1807.06607MaRDI QIDQ4993124FDOQ4993124

Authors: Richard Lang, Allan Lo 

Publication date: 15 June 2021

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: ErdH{o}s, Gy'arf'as and Pyber showed that every $r$-edge-coloured complete graph $K_n$ can be covered by $25r^{2}logr$ vertex-disjoint monochromatic cycles (independent of $n$). Here, we extend their result to the setting of binomial random graphs. That is, we show that if $p=p(n)=Omega(n^{-1/(2r)})$, then with high probability any $r$-edge-coloured $G(n,p)$ can be covered by at most $1000r^{4}logr$ vertex-disjoint monochromatic cycles. This answers a question of Kor'andi, Mousset, Nenadov, v{S}kori'{c} and Sudakov.

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

Recommendations

• Monochromatic cycle covers in random graphs
• An improved bound for the monochromatic cycle partition number
• Vertex coverings by monochromatic cycles and trees
• Monochromatic cycle partitions of edge-colored graphs
• Minimum degree conditions for monochromatic cycle partitioning

zbMATH Keywords

random graphmonochromatic cycle partition

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• \(R(C_n,C_n,C_n)\leqq (4+o(1))n\)
• Partitioning 2-edge-colored graphs by monochromatic paths and cycles
• An improved bound for the monochromatic cycle partition number
• Vertex coverings by monochromatic cycles and trees
• Partitioning complete bipartite graphs by monochromatic cycles
• Vertex covers by monochromatic pieces -- a survey of results and problems
• Monochromatic cycle partitions of edge-colored graphs
• Monochromatic cycle partitions of graphs with large minimum degree
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Title not available (Why is that?)
• Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles
• Partitioning 3-colored complete graphs into three monochromatic cycles
• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
• Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture
• Threshold Functions for Ramsey Properties
• Local colourings and monochromatic partitions in complete bipartite graphs
• Combinatorial theorems relative to a random set
• Minimum degree conditions for monochromatic cycle partitioning
• Partitioning random graphs into monochromatic components
• Monochromatic cycle covers in random graphs

Cited In (15)

• Minimum degree conditions for monochromatic cycle partitioning
• Partitioning random graphs into large cycles
• The monoid of the random graph
• An improved bound for the monochromatic cycle partition number
• Improved monochromatic loose cycle partitions in hypergraphs
• 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
• Partitioning a 2-edge-coloured graph of minimum degree \(2n/3 + o(n)\) into three monochromatic cycles
• Random graphs with monochromatic triangles in every edge coloring
• Covering 3-edge-colored random graphs with monochromatic trees
• Covering random graphs with monochromatic trees
• Bipartite Ramsey numbers of cycles for random graphs
• Covering graphs by monochromatic trees and Helly-type results for hypergraphs
• Partitioning random graphs into monochromatic components
• Bounded monochromatic components for random graphs

This page was built for publication: Monochromatic cycle partitions in random graphs

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