The multicolour size-Ramsey number of powers of paths

DOI10.1016/J.JCTB.2020.06.004zbMATH Open1448.05137arXiv1811.00844OpenAlexW3037609754WikidataQ122112546 ScholiaQ122112546MaRDI QIDQ2200928FDOQ2200928

Authors: Jie Han, Matthew Jenssen, Yoshiharu Kohayakawa, G. O. Mota, Barnaby Roberts 

Publication date: 24 September 2020

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

Abstract: Given a positive integer $s$, a graph $G$ is $s$-Ramsey for a graph $H$, denoted $Gightarrow(H{)}_s$, if every $s$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The $s$-colour size-Ramsey number ${hatr}_s(H)$ of a graph $H$ is defined to be ${hatr}_s(H)=min|E(G)|colonGightarrow(H{)}_s$. We prove that, for all positive integers $k$ and $s$, we have ${hatr}_s(P_n^k)=O(n)$, where $P_n^k$ is the $k$th power of the $n$-vertex path $P_n$.

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

Recommendations

• The size‐Ramsey number of powers of paths
• The size-Ramsey number of powers of bounded degree trees
• Note on the multicolour size-Ramsey number for paths
• scientific article; zbMATH DE number 1229599
• Remarks on the size Ramsey number of graphs

zbMATH Keywords

Ramseypowers of pathssize-Ramsey

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On maximal paths and circuits of graphs
• Expanding graphs contain all small trees
• On the combinatorial problems which I would most like to see solved
• The size Ramsey number
• Title not available (Why is that?)
• The size Ramsey number of a directed path
• On size Ramsey number of paths, trees, and circuits. I
• The Induced Size-Ramsey Number of Cycles
• An Alternative Proof of the Linearity of the Size-Ramsey Number of Paths
• The size-Ramsey number of trees
• On size Ramsey numbers of graphs with bounded degree
• Sparse partition universal graphs for graphs of bounded degree
• On a problem of K. Zarankiewicz
• Explicit construction of linear sized tolerant networks
• Calculating Ramsey Numbers by Partitioning Colored Graphs
• Title not available (Why is that?)
• The size-Ramsey number of trees
• The size Ramsey number of trees with bounded degree
• The Ramsey size number of dipaths
• Path Ramsey Number for Random Graphs
• Recent developments in graph Ramsey theory
• On some Multicolor Ramsey Properties of Random Graphs
• Note on the multicolour size-Ramsey number for paths
• The size‐Ramsey number of powers of paths
• The size Ramsey number of short subdivisions of bounded degree graphs

Cited In (12)

• The size‐Ramsey number of cubic graphs
• The size‐Ramsey number of powers of bounded degree trees
• Lower bounds of size Ramsey number for graphs with small independence number
• The size‐Ramsey number of short subdivisions
• Title not available (Why is that?)
• On the size-Ramsey number of grids
• Ramsey Goodness of Clique Versus Paths in Random Graphs
• Random cyclic triangle-free graphs of prime order
• Note on the multicolour size-Ramsey number for paths
• The multicolor size-Ramsey numbers of cycles
• The size-Ramsey number of 3-uniform tight paths
• The Size Ramsey Number of Graphs with Bounded Treewidth

This page was built for publication: The multicolour size-Ramsey number of powers of paths

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