Ramsey Goodness of Bounded Degree Trees

DOI10.1017/S0963548317000554zbMATH Open1388.05120arXiv1611.02688OpenAlexW2963974761MaRDI QIDQ4635503FDOQ4635503

Alexey Pokrovskiy, Benny Sudakov, Igor Balla

Publication date: 23 April 2018

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

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)$.

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tree embeddings
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Expanding graphs contain all small trees
• Some remarks on the theory of graphs
• Ramsey Numbers Involving Graphs with Long Suspended Paths
• Ramsey goodness and beyond
• Ramsey-goodness -- and otherwise
• Embedding Spanning Trees in Random Graphs
• Multipartite graph-sparse graph Ramsey numbers
• Ramsey goodness of paths
• Generalizations of a Ramsey-theoretic result of chvátal
• The Cycle-Complete Graph Ramsey Numbers
• Ramsey numbers of cubes versus cliques
• The Ramsey number of the clique and the hypercube

Cited In (10)

• Degree Ramsey numbers of closed blowups of trees
• Degree Ramsey numbers for cycles and blowups of trees
• A large tree is \(tK_m\)-good
• Ramsey Goodness of Cycles
• Ramsey goodness of paths
• The multicolor size-Ramsey numbers of cycles
• Ramsey numbers of large books versus multipartite graphs
• Degree conditions for Ramsey goodness of paths
• The Ramsey number for a forest versus disjoint union of complete graphs
• On the Size-Ramsey Number 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)