Equitable 2-colourability conjecture for even cycle decompositions

About 3 years old · traced to

Let v≥ℓ≥4v\geq \ell\geq 4 be even integers, and let II be a 1-factor of KvK_v. An equitably 2-colourable ℓ\ell-cycle decomposition of Kv−IK_v-I is an ℓ\ell-cycle decomposition whose vertices admit a red-blue colouring with colour classes differing in size by at most one on each cycle. The divisibility condition is that ℓ\ell divides the number of edges of Kv−IK_v-I:

ℓ∣v(v−2)2.\ell\mid \frac{v(v-2)}{2}.

Even-cycle equitable-colourability conjecture. There exists an equitably 2-colourable ℓ\ell-cycle decomposition of Kv−IK_v-I if and only if

ℓ∣v(v−2)2.\ell\mid \frac{v(v-2)}{2}.

The paper leaves the more general existence question for equitably 2-colourable odd cycle decompositions of the cocktail party graph open; the stated even-order conjecture is likewise presented as unresolved.

References

Primary source

Andrea Burgess and Francesca Merola, “On equitably 2-colourable odd cycle decompositions”, arXiv:2309.15628 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.