Inducibility of rainbow graphs

2024/05/06 by Emily Cairncross, Cairncross, Emily, Clayton Mizgerd +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2405.03112

Abstract

Fix k≥ 11 and a rainbow k-clique R. We prove that the inducibility of R is k!/(k^k-k). An extremal construction is a balanced recursive blow-up of R. This answers a question posed by Huang, that is a generalization of an old problem of Erd\H os and Sós. It remains open to determine the minimum k for which our result is true. More generally, we prove that there is an absolute constant C>0 such that every k-vertex connected rainbow graph with minimum degree at least Clog k has inducibility k!/(k^k-k).

Cited by

• Density of rainbow triangles and properly colored K₄'s

Related

• New Hardness Results in Rainbow Connectivity
• On the proper rainbow saturation numbers of cliques, paths, and odd cycles
• Rainbow Erdős-Sós Conjectures
• Rainbow cycles in properly edge-colored graphs
• Note on the upper bound of the rainbow index of a graph