Coloring triangles in graphs

2024/11/20 by Ayush Basu, Basu, Ayush, Vojtěch Rödl +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2411.13416

openalex publication_date 2024/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study quantitative aspects of the following fact: For every graph F, there exists a graph G with the property that any 2-coloring of the triangles of G yields an induced copy of F, in which all triangles are monochromatic. We define the Ramsey number R_ind^Δ(F) as the smallest size of such a graph G. Although this fact has several proofs, all of them provide tower-type bounds. We study the number R_ind^Δ(F) for some particular classes of graphs F.

Related

• Triangle Ramsey numbers of complete graphs
• Recent developments in graph Ramsey theory
• On bounded degree graphs with large size-Ramsey numbers
• Three early problems on size Ramsey numbers
• New bounds for some small multicolor Ramsey numbers