Majority edge-colorings of graphs (Q2692181)

Summary: 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.