Monochromatic cycle partitions in random graphs

DOI10.1017/S0963548320000401MaRDI QIDQ4993124zbMATH OpenFDO

Authors Richard Lang, Allan Lo

Publication date 15 June 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1208722 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• An improved bound for the monochromatic cycle partition number
• Combinatorial theorems relative to a random set
• Local colourings and monochromatic partitions in complete bipartite graphs
• Minimum degree conditions for monochromatic cycle partitioning
• Monochromatic cycle covers in random graphs
• Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\)
• Monochromatic cycle partitions of edge-colored graphs
• Monochromatic cycle partitions of graphs with large minimum degree
• Partitioning 2-edge-colored graphs by monochromatic paths and cycles
• Partitioning 3-colored complete graphs into three monochromatic 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 complete bipartite graphs by monochromatic cycles
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Partitioning random graphs into monochromatic components
• Threshold Functions for Ramsey Properties
• Vertex coverings by monochromatic cycles and trees
• Vertex covers by monochromatic pieces -- a survey of results and problems
• \(R(C_n,C_n,C_n)\leqq (4+o(1))n\)

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
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
• 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)