Induced Ramsey problems for trees and graphs with bounded treewidth

2024/06/01 by Zach Hunter, Benny Sudakov, Hunter, Zach +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2406.00352

openalex publication_date 2024/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The induced q-color size-Ramsey number r_ind(H;q) of a graph H is the minimal number of edges a host graph G can have so that every q-edge-coloring of G contains a monochromatic copy of H which is an induced subgraph of G. A natural question, which in the non-induced case has a very long history, asks which families of graphs H have induced Ramsey numbers that are linear in |H|. We prove that for every k,w,q, if H is an n-vertex graph with maximum degree k and treewidth at most w, then r_ind(H;q) = O_k,w,q(n). This extends several old and recent results in Ramsey theory. Our proof is quite simple and relies upon a novel reduction argument.

Related

• Effective bounds for induced size-Ramsey numbers of cycles
• An exponential upper bound for induced Ramsey numbers
• On bounded degree graphs with large size-Ramsey numbers
• Three early problems on size Ramsey numbers
• On two problems in graph Ramsey theory