On equitably 2-colourable odd cycle decompositions

2023/09/27 by Burgess, Andrea, Merola, Francesca · 1 citation
#05B30 #05C15 #05C51 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2309.15628

Abstract

An ℓ-cycle decomposition of K_v is said to be equitably 2-colourable if there is a 2-vertex-colouring of K_v such that each colour is represented (approximately) an equal number of times on each cycle: more precisely, we ask that in each cycle C of the decomposition, each colour appears on \lfloor ℓ/2 \rfloor or \lceil ℓ/2 \rceil of the vertices of C. In this paper we study the existence of equitably 2-colourable ℓ-cycle decompositions of K_v, where ℓ is odd, and prove the existence of such a decomposition for v ≡ 1, ℓ (mod 2ℓ).

Cited by

• Colourings of Uniform Group Divisible Designs and Maximum Packings

Related

• A reduction of the "cycles plus K₄'s" problem
• Between 2- and 3-colorability
• Unavoidable patterns in locally balanced colourings
• Repeated patterns in proper colourings
• Monochromatic cycle partitions of 2-coloured graphs with minimum degree 3n/4