On Color Isomorphic Pairs in Proper Edge Colourings of Complete Graphs

2022/01/03 by Xiao‐Chuan Liu, Yang Xu, Liu, Xiao-Chuan +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2201.00838

openalex publication_date 2022/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Following the recent paper which initiated the study of colour isomorphism problems for complete graphs, we obtain upper bounds for f₂(n,H) for a family of graphs H obtained as the K₀-th rooted power of a balanced rooted tree for some sufficiently large K₀. The proof uses the random polynomial method of Bukh. We also obtain matching lower bounds for 1-subdivisions of the complete bipartite graph.

Related

• On color isomorphic subdivisions
• Color isomorphic even cycles and a related Ramsey problem
• A rooted variant of Stanley's chromatic symmetric function
• Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph
• Rainbow Subgraphs in Edge-colored Complete Graphs -- Answering two Questions by Erdős and Tuza