2025/11/16 by Allan Lo, Klas Markström, Lo, Allan +9
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.2511.12505
openalex publication_date 2025/11/16 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28
An edge-colouring of a graph G can fail to be rainbow for two reasons: either it contains a monochromatic cherry (a pair of incident edges), or a monochromatic matching of size two. A colouring is a proper colouring if it forbids the first structure, and a star-colouring if it forbids the second structure. In this paper, we study rainbow subgraphs in star-coloured graphs and determine the maximum number of colours in a star-colouring of a large complete graph which does not contain a rainbow copy of a given graph H. This problem is a special case of one studied by Axenovich and Iverson on generalised Ramsey numbers and we extend their results in this case.