Large monochromatic components of small diameter

DOI10.1002/JGT.22739MaRDI QIDQ6056809zbMATH OpenOpenAlexFDO

Authors Erik Carlson, Ryan R. Martin, Bo Peng, Miklós Ruszinkó

Publication date 4 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

zbMATH Keywords

diametermonochromatic componentRamsey theory

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: Gy'arf'as conjectured in 2011 that every $r$-edge-colored $K_n$ contains a monochromatic component of bounded ("perhaps three") diameter on at least $n/(r-1)$ vertices. Letzter proved this conjecture with diameter four. In this note we improve the result in the case of $r=3$: We show that in every $3$-edge-coloring of $K_n$ either there is a monochromatic component of diameter at most three on at least $n/2$ vertices or every color class is spanning and has diameter at most four.

Recommendations

• Monochromatic diameter-2 components in edge colorings of the complete graph
• Large monochromatic components in edge colored graphs with a minimum degree condition
• Large components in r-edge-colorings of K_n have diameter at most five
• Monochromatic components in edge-coloured graphs with large minimum degree
• Covering complete graphs by monochromatically bounded sets

Cites work

• Covering the complete graph by partitions
• Finding large \(p\)-colored diameter two subgraphs
• Generalizing the Ramsey problem through diameter
• Large components in r-edge-colorings of K_n have diameter at most five
• Large monochromatic components in edge colorings of graphs: A survey
• Large monochromatic triple stars in edge colourings
• Monochromatic diameter-2 components in edge colorings of the complete graph
• Size of monochromatic double stars in edge colorings

Cited in

(5)

• Monochromatic diameter-2 components in edge colorings of the complete graph
• Large components in r-edge-colorings of K_n have diameter at most five
• Covering complete graphs by monochromatically bounded sets
• Low diameter monochromatic covers of complete multipartite graphs
• Balanced substructures in bicolored graphs

This page was built for publication: Large monochromatic components of small diameter

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