{"id":"arxiv/2608.04122","url":"https://arxiv.org/abs/2608.04122","tags":["math.CO"],"score":0,"title":"On Strong Majority Edge Colourings with Few Colours","domain":"math.CO","source":"arxiv","authors":["Paweł Pękała","Jakub Przybyło"],"reviews":0,"subject":"math.CO","summary":"A strong majority edge colouring of a graph $G$ is an edge colouring in which, for every edge $e$ and every colour $α$, at most half the edges adjacent to $e$ receive colour $α$. 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-04","reactions":{}}