On-line majority edge-colourings of graphs

Source abstract

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 colours, is optimal among on-line algorithms if $δ= O(\frac{\log n}{\log\log n})$. We further extend our results to $1/k$-majority edge-colourings.