The size-Ramsey number of powers of bounded degree trees

Given a positive integer \(s\), the \(s\)-colour size-Ramsey number of a graph \(H\) is the smallest integer \(m\) such that there exists a graph \(G\) with \(m\) edges with the property that, in any colouring of \(E(G)\) with \(s\) colours, there is a monochromatic copy of \(H\). We prove that, for...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-07
Main Authors: Berger, Sören, Kohayakawa, Yoshiharu, Maesaka, Giulia Satiko, Martins, Taísa, Mendonça, Walner, Guilherme Oliveira Mota, Parczyk, Olaf
Format: Article
Language:English
Subjects:
Color
Coloring
Graph theory
Graphs
Integers
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a positive integer \(s\), the \(s\)-colour size-Ramsey number of a graph \(H\) is the smallest integer \(m\) such that there exists a graph \(G\) with \(m\) edges with the property that, in any colouring of \(E(G)\) with \(s\) colours, there is a monochromatic copy of \(H\). We prove that, for any positive integers \(k\) and \(s\), the \(s\)-colour size-Ramsey number of the \(k\)th power of any \(n\)-vertex bounded degree tree is linear in \(n\). As a corollary we obtain that the \(s\)-colour size-Ramsey number of \(n\)-vertex graphs with bounded treewidth and bounded degree is linear in \(n\), which answers a question raised by Kamčev, Liebenau, Wood and Yepremyan [The size Ramsey number of graphs with bounded treewidth, arXiv:1906.09185 (2019)].
ISSN:2331-8422
DOI:10.48550/arxiv.1907.03466