2023/09/28 by Paweł Pękała, Pękała, Paweł, Jakub Przybyło +1 · 1 citation
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2309.16624
openalex publication_date 2023/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A (1)/(k)-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 (1)/(k)'th of the edges incident with v have colour i. We conjecture that for every integer k≥ 2, each graph with minimum degree δ≥ k2 is (1)/(k)-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 2k2 instead of k2, 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 k3log k, 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 2k2 by ((7)/(4)+o(1))k2. Finally, we provide the proof of the conjecture itself for k≤ 4 and completely solve an analogous problem for the family of bipartite graphs.