{"id":"arxiv/2609.37973","url":"https://arxiv.org/abs/2609.37973","tags":["math.CO"],"score":0,"title":"On-line majority edge-colourings of graphs","domain":"math.CO","source":"arxiv","authors":["Paweł Pękała"],"reviews":0,"subject":"math.CO","summary":"A majority edge-colouring of a graph $G$ is a colouring of the edges of $G$ such that, for every vertex $v$ of $G$, at most half of the edges incident with $v$ receive the same colour. This notion was introduced by Bock et al. in 2023, who proved that every graph of minimum degree at least $2$ has a majority $4$-edge-colouring. We investigate an on-line variant of majority edge-colouring in which the graph is revealed by the Presenter edge-by-edge and the Algorithm must colour each edge immediately and irrevocably. In particular. we prove that the greedy strategy, which uses at most five…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}