| Autor: |
Bock, Felix, Kalinowski, Rafał, Pardey, Johannes, Pilśniak, Monika, Rautenbach, Dieter, Woźniak, Mariusz |
| Rok vydání: |
2022 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
