Majority Edge-Colorings of Graphs

Felix Bock, Rafał Kalinowski, Johannes Pardey +3

We propose the notion of a majority $k$-edge-coloring of a graph $G$, which is an edge-coloring of $G$ with $k$ colors such that, for every vertex $u$ of $G$, at most half the edge…