The odd-order dense quasirandom edge-colouring conjecture

For 0<p<10<p<1, suppose there exist ε,η>0\varepsilon,\eta>0 and n0Nn_0\in\mathbb{N} such that GG is a lower-(p,ε)(p,\varepsilon)-regular graph on nn0n\geq n_0 vertices, nn is odd, and Δ(G)δ(G)ηn\Delta(G)-\delta(G)\leq\eta n. Odd-order quasirandom edge-colouring conjecture. Under these hypotheses,

χ(G)=Δ(G)if and only ifxV(G)(Δ(G)dG(x))Δ(G).\chi'(G)=\Delta(G)\quad\text{if and only if}\quad \sum_{x\in V(G)}\bigl(\Delta(G)-d_G(x)\bigr)\geq\Delta(G).

This is presented as an interesting possible analogue of the even-order quasirandom result; the source does not claim it as proved.

Sources & referencesView supporting material

Primary source

Stefan Glock, Daniela Kühn and Deryk Osthus, “Optimal path and cycle decompositions of dense quasirandom graphs”, arXiv:1503.00494 (2016).

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.