On Alternating 6-Cycles in Edge-Coloured Graphs

2025/05/14 by Hao Chen, Jonathan A. Noel, Chen, Hao +1 · 2 citations
#math.CO #cs.DM

paper · pdf · doi:10.48550/arxiv.2505.09809

Abstract

In this short note, we use flag algebras to prove that the number of colour alternating 6-cycles in a red/blue colouring of a large clique is asymptotically maximized by a uniformly random colouring. This settles the first open case of a problem of Basit, Granet, Horsley, Kündgen and Staden.

Cited by

• Semi-inducibility of 4-vertex graphs
• The semi-inducibility of the blue--blue--red path on four vertices

Related

• Clique colouring of binomial random graphs
• Colour-biased Hamilton cycles in random graphs
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• Strong edge-colouring via local flag algebras
• Colouring random graphs: Tame colourings