On globally sparse Ramsey graphs

DOI10.1016/J.DISC.2013.07.023MaRDI QIDQ393934zbMATH OpenOpenAlexFDO

Authors Torsten Mütze, Ueli Peter

Publication date 24 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey theoryarboricitygraph densityNash-Williams theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Generalized Ramsey theory (05C55)

Abstract: We say that a graph $G$ has the Ramsey property w.r.t. some graph $F$ and some integer $rgeq2$, or $G$ is $(F,r)$-Ramsey for short, if any $r$-coloring of the edges of $G$ contains a monochromatic copy of $F$. R{"o}dl and Ruci{'n}ski asked how globally sparse $(F,r)$-Ramsey graphs $G$ can possibly be, where the density of $G$ is measured by the subgraph $HsubseteqG$ with the highest average degree. So far, this so-called Ramsey density is known only for cliques and some trivial graphs $F$. In this work we determine the Ramsey density up to some small error terms for several cases when $F$ is a complete bipartite graph, a cycle or a path, and $rgeq2$ colors are available.

Recommendations

• Globally sparse vertex‐ramsey graphs
• Independence numbers of locally sparse graphs and a Ramsey type problem
• The Ramsey number of dense graphs
• Multipartite graph-sparse graph Ramsey numbers
• Two variants of the size Ramsey number

Cites work

• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 125471 (Why is no real title available?)
• scientific article; zbMATH DE number 524135 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Decomposition of Finite Graphs Into Forests
• Density theorems for bipartite graphs and related Ramsey-type results
• Generalized Ramsey Theory for Graphs. II. Small Diagonal Numbers
• Globally sparse vertex‐ramsey graphs
• Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
• New lower bounds on the multicolor Ramsey numbers \(R_{r}(C_{2m})\)
• On multicolor Ramsey numbers for complete bipartite graphs
• On the Folkman Numberf(2, 3, 4)
• On the minimum degree of minimal Ramsey graphs
• On the multi-colored Ramsey numbers of cycles
• Ramsey numbers for cycles in graphs
• Random graphs.
• Star arboricity
• The Induced Size-Ramsey Number of Cycles
• The Ramsey property for graphs with forbidden complete subgraphs
• The minimum degree of Ramsey-minimal graphs
• The star arboricity of graphs
• Two variants of the size Ramsey number

Cited in

(7)

• Sparse Ramsey graphs
• On Ramsey Numbers of Sparse Graphs
• The Size Ramsey Number of Graphs with Bounded Treewidth
• Minimal ordered Ramsey graphs
• The Ramsey number of dense graphs
• Density theorems for bipartite graphs and related Ramsey-type results
• Globally sparse vertex‐ramsey graphs

This page was built for publication: On globally sparse Ramsey graphs

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