Geodesic
Majority edge-colorings of graphs
The electronic journal of combinatorics, Tome 30 (2023) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/11291
Classification : 05C15, 05C07, 05C35
Mots-clés : unfriendly partition conjecture, majority 3-edge-coloring 
@article{10_37236_11291,
     author = {Felix Bock and Rafa{\l} Kalinowski and Johannes Pardey and Monika Pil\'sniak and Dieter Rautenbach and Mariusz Wo\'zniak},
     title = {Majority edge-colorings of graphs},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {1},
     doi = {10.37236/11291},
     zbl = {1510.05069},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11291/}
}
TY  - JOUR
AU  - Felix Bock
AU  - Rafał Kalinowski
AU  - Johannes Pardey
AU  - Monika Pilśniak
AU  - Dieter Rautenbach
AU  - Mariusz Woźniak
TI  - Majority edge-colorings of graphs
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11291/
DO  - 10.37236/11291
ID  - 10_37236_11291
ER  - 
%0 Journal Article
%A Felix Bock
%A Rafał Kalinowski
%A Johannes Pardey
%A Monika Pilśniak
%A Dieter Rautenbach
%A Mariusz Woźniak
%T Majority edge-colorings of graphs
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11291/
%R 10.37236/11291
%F 10_37236_11291
Felix Bock; Rafał Kalinowski; Johannes Pardey; Monika Pilśniak; Dieter Rautenbach; Mariusz Woźniak. Majority edge-colorings of graphs. The electronic journal of combinatorics, Tome 30 (2023) no. 1. doi: 10.37236/11291

Cité par Sources :