On Generalised Majority Edge-Colourings of Graphs - Pękała, Paweł; Przybyło, Jakub (The Electronic Journal of Combinatorics, 2024)
A 1k-majority l-edge-colouring of a graph G is a colouring of its edges with l colours such that for every colour i and each vertex v of G, at most 1k’th of the edges incident with v have colour i. We conjecture that for every integer k≥ 2, each graph with minimum degree δ≥ k^2 is 1k-majority (k+1)-edge-colourable and observe that such result would be best possible. This was already known to hold for k=2. We support the conjecture by proving it with 2k^2 instead of k^2, which confirms the right order of magnitude of the conjectured optimal lower bound for δ. We at the same time improve the previously known bound of order k^3k, based on a straightforward probabilistic approach. As this technique seems not applicable towards any further improvement, we use a more direct non-random approach. We also strengthen our result, in particular substituting 2k^2 by (74+o(1))k^2. Finally, we provide the proof of the conjecture itself for k≤ 4 and completely solve an analogous problem for the family of bipartite graphs.