Majority Edge-Colorings of Graphs

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

This page was built for publication: Majority Edge-Colorings of Graphs