2022/05/23 by Bock, Felix, Kalinowski, Rafał, Pardey, Johannes +3 · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2205.11125
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 edges of G incident with u have the same color. We show the best possible results that every graph of minimum degree at least 2 has a majority 4-edge-coloring, and that every graph of minimum degree at least 4 has a majority 3-edge-coloring. Furthermore, we discuss a natural variation of majority edge-colorings and some related open problems.