Ramsey goodness of paths

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

Authors: Alexey Pokrovskiy, Benny Sudakov 

Publication date: 25 November 2016

Published in: Journal of Combinatorial Theory. Series B (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 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.

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

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

zbMATH Keywords

Ramsey numbersexpandersRamsey goodnesspaths in graphs

Mathematics Subject Classification ID

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

Cites Work

• Some remarks on the theory of graphs
• Calculating Ramsey numbers by partitioning colored graphs
• Hamiltonian circuits in random graphs
• Ramsey Numbers Involving Graphs with Long Suspended Paths
• Title not available (Why is that?)
• Ramsey goodness and beyond
• Ramsey-goodness -- and otherwise
• Multipartite graph-sparse graph Ramsey numbers
• Global connectivity and expansion: long cycles and factors in \(f\)-connected graphs
• Ramsey goodness of paths
• Generalizations of a Ramsey-theoretic result of chvátal
• On cycle—Complete graph ramsey numbers
• Ramsey goodness of bounded degree trees
• The Cycle-Complete Graph Ramsey Numbers
• Ramsey numbers of cubes versus cliques
• The Ramsey number of the clique and the hypercube
• On the path-complete bipartite Ramsey number
• Ramsey numbers involving a long path

Cited In (21)

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