On-line majority edge-colourings of graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.37973
curl -X POST /api/v1/records/arxiv/2609.37973/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.37973/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'