Majority Edge-Colorings of Graphs

DOI10.37236/11291arXiv2205.11125MaRDI QIDQ6399894FDOQ6399894

Authors: Felix Bock, Rafał Kalinowski, Johannes Pardey, Monika Pilśniak, Dieter Rautenbach, Mariusz Woźniak 

Publication date: 23 May 2022

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.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6399894)