{"id":"arxiv/2604.20752","url":"https://arxiv.org/abs/2604.20752","tags":["math.CO"],"score":0,"title":"Majority C-coloring of graphs","domain":"math.CO","source":"arxiv","authors":["Csilla Bujtas","Magda Dettlaff","Hanna Furmanczyk","Aleksandra Laskowska"],"reviews":0,"subject":"math.CO","summary":"Inspired by the majority colorings and C-colorings, we introduce and study the majority C-coloring of graphs. In such a vertex coloring, every vertex shares its color with at least half of its neighbors. The maximum number of colors that can be used in a majority C-coloring of a graph $G$ is called the majority C-chromatic number and denoted by $\\mc(G)$. An upper bound on $\\mc(G)$ is proved in terms of the order, minimum, and maximum degree. Its sharpness is demonstrated by several results over different graph classes. In particular, $\\mc(P_n^k)= \\mc(C_n^k)= \\lfloor n/(k+1)\\rfloor$ is true…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-22","reactions":{}}