Monochromatic trees in random graphs

DOI10.1017/S0305004117000846zbMATH Open1379.05025arXiv1611.10299OpenAlexW2964254121WikidataQ101496530 ScholiaQ101496530MaRDI QIDQ1690004FDOQ1690004

Authors: M. Schacht, Yoshiharu Kohayakawa, G. O. Mota 

Publication date: 18 January 2018

Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

Abstract: Bal and DeBiasio [Partitioning random graphs into monochromatic components, Electron. J. Combin. 24 (2017), Paper 1.18] put forward a conjecture concerning the threshold for the following Ramsey-type property for graphs $G$: every $k$-colouring of the edge set of $G$ yields $k$ pairwise vertex disjoint monochromatic trees that partition the whole vertex set of $G$. We determine the threshold for this property for two colours.

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

Recommendations

• Monochromatic trees in random graphs
• Partitioning by monochromatic trees
• Random graphs with monochromatic triangles in every edge coloring
• Covering 3-edge-colored random graphs with monochromatic trees
• Monochromatic trees in random tournaments

zbMATH Keywords

Ramsey theoryrandom graphs

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random graphs.
• Graph theory
• Sharp thresholds of graph properties, and the $k$-sat problem
• Monochromatic trees in random graphs
• Partitioning random graphs into monochromatic components

Cited In (17)

• Remarks on a Ramsey theory for trees
• Monochromatic trees in random graphs
• Title not available (Why is that?)
• The monoid of the random graph
• Generalizations and strengthenings of Ryser's conjecture
• Monochromatic trees in random tournaments
• The smallest Ramsey numbers
• Special monochromatic trees in two-colored complete graphs
• Covering 3-edge-colored random graphs with monochromatic trees
• Covering 3-coloured random graphs with monochromatic trees
• Covering random graphs with monochromatic trees
• Vertex covering with monochromatic pieces of few colours
• Ramsey goodness of trees in random graphs
• Partitioning random graphs into monochromatic components
• Title not available (Why is that?)
• Bounded monochromatic components for random graphs
• Monochromatic cycle partitions in random graphs

This page was built for publication: Monochromatic trees in random graphs

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