The Size Ramsey Number of Graphs with Bounded Treewidth

Abstract: A graph

G

is Ramsey for a graph

H

if every 2-colouring of the edges of

G

contains a monochromatic copy of

H

. We consider the following question: if

H

has bounded treewidth, is there a `sparse' graph

G

that is Ramsey for

H

? Two notions of sparsity are considered. Firstly, we show that if the maximum degree and treewidth of

H

are bounded, then there is a graph

G

with

O (| V (H) |)

edges that is Ramsey for

H

. This was previously only known for the smaller class of graphs

H

with bounded bandwidth. On the other hand, we prove that the treewidth of a graph

G

that is Ramsey for

H

cannot be bounded in terms of the treewidth of

H

alone. In fact, the latter statement is true even if the treewidth is replaced by the degeneracy and

H

is a tree.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: The Size Ramsey Number of Graphs with Bounded Treewidth