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

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.

Sources & referencesView supporting material

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.