Ramsey goodness of paths

DOI10.1016/J.JCTB.2016.06.009zbMATH Open1350.05101OpenAlexW2963629695MaRDI QIDQ345089FDOQ345089

Authors Alexey Pokrovskiy, Benny Sudakov

Publication date 25 November 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey numbersexpandersRamsey goodnesspaths in graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

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 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$ 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 short note we prove that $n$-vertex path $P_n$ is $H$-good for all $ngeq4|H|$. This proves in a strong form a conjecture of Allen, Brightwell, and Skokan.

Recommendations

• On the Ramsey-goodness of paths
• Ramsey goodness of cycles
• Ramsey numbers involving a long path
• Ramsey good graphs with long suspended paths
• Ramsey goodness of bounded degree trees

Cites work

• scientific article; zbMATH DE number 3545699 (Why is no real title available?)
• Calculating Ramsey numbers by partitioning colored graphs
• Generalizations of a Ramsey-theoretic result of chvátal
• Global connectivity and expansion: long cycles and factors in \(f\)-connected graphs
• Hamiltonian circuits in random graphs
• Multipartite graph-sparse graph Ramsey numbers
• On cycle—Complete graph ramsey numbers
• On the path-complete bipartite Ramsey number
• Ramsey Numbers Involving Graphs with Long Suspended Paths
• Ramsey goodness and beyond
• Ramsey goodness of bounded degree trees
• Ramsey goodness of paths
• Ramsey numbers involving a long path
• 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

Cited in

(21)

• Ramsey numbers involving a long path
• Maximum clique deleted from Ramsey graphs of a graph and paths
• A large tree is \(tK_m\)-good
• Ramsey goodness of paths
• The Size Ramsey Number of Graphs with Bounded Treewidth
• Ramsey good graphs with long suspended paths
• The Ramsey number for a forest versus disjoint union of complete graphs
• Degree conditions for Ramsey goodness of paths
• Complexity of Computing the Anti-Ramsey Numbers for Paths.
• Ramsey numbers of large books versus multipartite graphs
• Large generalized books are \(p\)-good
• Ramsey goodness of bounded degree trees
• The goodness of long path with respect to multiple copies of complete graphs
• The size-Ramsey number of powers of bounded degree trees
• On the Ramsey-goodness of paths
• Ramsey goodness of cycles
• The extremal function for cycles of length \(\ell\) mod \(k\)
• Calculating Ramsey numbers by partitioning colored graphs
• Ramsey goodness of clique versus paths in random graphs
• Ramsey numbers of cycles versus general graphs
• A Ramsey goodness result for graphs with large pendent trees

This page was built for publication: Ramsey goodness of paths

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