{"id":"arxiv/2605.23828","url":"https://arxiv.org/abs/2605.23828","tags":["math.CO"],"score":0,"title":"Strong majority colorings of graphs","domain":"math.CO","source":"arxiv","authors":["Rafał Kalinowski","Mateusz Kamyczura","Monika Pilśniak","Mariusz Woźniak"],"reviews":0,"subject":"math.CO","summary":"Motivated by majority vertex-colorings of graphs and digraphs and majority edge-colorings of graphs, we introduce two concepts of strong majority colorings. A strong majority vertex-coloring of a graph $G=(V,E)$ is a mapping $c:V\\rightarrow C$ such that for every vertex $v\\in V$ and every color $α\\in C$, at most half of the neighbors of $v$ have color $α$. The strong majority number of $G$, denoted Maj$(G)$, is the least number of colors in such a coloring. We show that Maj$(G)$ can be arbitrarily large and prove a tight upper bound Maj$(G)\\le 2Δ(G)+1$ for every graph $G$ without pendant…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-22","reactions":{}}