On Strong Majority Edge Colourings with Few Colours

Abstract

A strong majority edge colouring of a graph $G$ is an edge colouring in which, for every edge $e$ and every colour $\alpha$, at most half the edges adjacent to $e$ receive colour $\alpha$. Like many related colouring notions, it admits a natural interpretation as a colouring problem for an associated hypergraph. Somewhat surprisingly, although the corresponding hypergraph may have arbitrarily large vertex degrees, a universal finite upper bound on the sufficient number of colours in a strong majority edge colouring exists under a natural modest minimum degree assumption, unlike in several other closely related majority concepts. We in particular prove that every graph $G$ with minimum degree $\delta \ge 5$ admits a strong majority edge colouring with three colours, improving both the previously known bound $\delta \ge 9$ for three colours and the result showing that four colours suffice whenever $\delta \ge 5$. Our result is best possible with respect to the number of colours and the minimum degree assumption. We also introduce a more general framework of strong $1/k$-majority edge colourings and establish corresponding bounds for this setting.

14 pages