Ramsey goodness of bounded degree trees

DOI10.1017/S0963548317000554MaRDI QIDQ4635503zbMATH OpenOpenAlexFDO

Authors Igor Balla, Alexey Pokrovskiy, Benny Sudakov

Publication date 23 April 2018

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

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

Mathematics Subject Classification ID

Trees (05C05) Generalized Ramsey theory (05C55)

Abstract: Given a pair of graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest $N$ such that every red-blue coloring of the edges of the complete graph $K_N$ contains a red copy of $G$ or a blue copy of $H$. If a graph $G$ is connected, it is well known and easy to show that $R(G,H)geq(|G|-1)(chi(H)-1)+sigma(H)$, where $chi(H)$ is the chromatic number of $H$ and $sigma(H)$ is the size of the smallest color class in a $chi(H)$-coloring of $H$. A graph $G$ is called $H$-good if $R(G,H)=(|G|-1)(chi(H)-1)+sigma(H)$. The notion of Ramsey goodness was introduced by Burr and ErdH{o}s in 1983 and has been extensively studied since then. In this paper we show that if $ngeqOmega(|H|lo{g}^4|H|)$ then every $n$-vertex bounded degree tree $T$ is $H$-good. The dependency between $n$ and $|H|$ is tight up to $log$ factors. This substantially improves a result of ErdH{o}s, Faudree, Rousseau, and Schelp from 1985, who proved that $n$-vertex bounded degree trees are $H$-good when when $ngeqOmega(|H{|}^4)$.

Recommendations

• Ramsey goodness of paths
• Ramsey goodness of cycles
• A large tree is \(tK_m\)-good
• scientific article; zbMATH DE number 3885958
• scientific article; zbMATH DE number 568795

Cites work

• scientific article; zbMATH DE number 3871407 (Why is no real title available?)
• scientific article; zbMATH DE number 16297 (Why is no real title available?)
• scientific article; zbMATH DE number 3545699 (Why is no real title available?)
• scientific article; zbMATH DE number 568795 (Why is no real title available?)
• scientific article; zbMATH DE number 1118889 (Why is no real title available?)
• Embedding spanning trees in random graphs
• Expanding graphs contain all small trees
• Generalizations of a Ramsey-theoretic result of chvátal
• Multipartite graph-sparse graph Ramsey numbers
• Ramsey Numbers Involving Graphs with Long Suspended Paths
• Ramsey goodness and beyond
• Ramsey goodness of paths
• Ramsey numbers of cubes versus cliques
• Ramsey-goodness -- and otherwise
• Some remarks on the theory of graphs
• The Cycle-Complete Graph Ramsey Numbers
• The Ramsey number of the clique and the hypercube
• The history of degenerate (bipartite) extremal graph problems
• Tree embeddings

Cited in

(22)

• Ramsey numbers of bounded degree trees versus general graphs
• Degree Ramsey numbers of closed blowups of trees
• A Ramsey goodness result for graphs with large pendent trees
• Ramsey numbers of stripes versus trees and unicyclic graphs
• Degree Ramsey numbers for cycles and blowups of trees
• Ramsey numbers for a large tree versus multiple copies of complete graphs of different sizes
• A large tree is \(tK_m\)-good
• On the size-Ramsey number of cycles
• Generalizations of a Ramsey-theoretic result of chvátal
• On tree-wheel Ramsey numbers
• Trees and \(n\)-good hypergraphs
• Ramsey goodness of paths
• A note on degree conditions for Ramsey goodness of paths
• scientific article; zbMATH DE number 3885958 (Why is no real title available?)
• Ramsey numbers of trees versus generalized wheels
• The multicolor size-Ramsey numbers of cycles
• Ramsey numbers of large books versus multipartite graphs
• Ramsey goodness of paths versus unbalanced graphs
• Ramsey goodness of trees in random graphs
• Degree conditions for Ramsey goodness of paths
• The Ramsey number for a forest versus disjoint union of complete graphs
• Ramsey goodness of cycles

This page was built for publication: Ramsey goodness of bounded degree trees

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