Cambie's bounded-overlap conjecture for simultaneous edge-colourings

About 2 years old · traced to

Let G1,…,GkG_1,\dots,G_k be graphs of maximum degree at most Δ\Delta, and let ℓ\ell be a positive integer such that every edge appears in at most ℓ\ell of the graphs. Let χ′(G1,…,Gk)\chi'(G_1,\dots,G_k) be the minimum number of colours in an edge-colouring of the union whose restriction to each graph is proper.

Cambie's conjecture. Then

χ′(G1,…,Gk)≤ϱ(ℓ)Δ+o(Δ).\chi'(G_1,\dots,G_k)\leq \varrho(\ell)\Delta+o(\Delta).

Here ϱ(ℓ)\varrho(\ell) is the extremal asymptotic coefficient for the corresponding bounded-edge-size hypergraph colouring problem, as defined in the paper. The paper states that its results establish this conjecture asymptotically.

References

Primary source

Simona Boyadzhiyska, Richard Lang, Allan Lo and Michael Molloy, “Simultaneous edge-colourings”, arXiv:2411.04071 (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.