2017/08/23 by Alexander Haupt, Haupt, Alexander, Damian Reding +1
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1708.07060
openalex publication_date 2017/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note we study graphs Gr with the property that every colouring of E(Gr) with r+1 colours admits a copy of some graph H using at most r colours. For 1≤ r≤ e(H) such graphs occur naturally at intermediate steps in the synthesis of a 2-colour Ramsey graph G1\longrightarrow H. (The corresponding notion of Ramsey-type numbers was introduced by Erdös, Hajnal and Rado in 1965 and subsequently studied by Erdös and Szemerédi in 1972). For H=Kn we prove a result on building a Gr from a Gr+1 and establish Ramsey-infiniteness. From the structural point of view, we characterise the class of the minimal Gr in the case when H is relaxed to be the graph property of containing a cycle; we then use it to progress towards a constructive description of that class by proving both a reduction and an extension theorem.