{"id":"arxiv/2609.25128","url":"https://arxiv.org/abs/2609.25128","tags":["math.CO"],"score":0,"title":"Sub-quorum colorings of graphs","domain":"math.CO","source":"arxiv","authors":["Haobo Ma","Rafik Sahbi","Zhang Wenlin"],"reviews":0,"subject":"math.CO","summary":"A sub-quorum coloring is a partial vertex coloring in which every colored vertex sees at least half of its colored closed neighborhood in its own color. We study the maximum number of colors $\\psq(G)$ from structural, algorithmic and extremal viewpoints. Every $2$-independent set yields a sub-quorum coloring, so $\\psq(G)\\geβ_2(G)$. We prove the degree bound $\\psq(G)\\le Δ(G)|V(G)|/(Δ(G)+δ(G)-1)$ for $δ(G)\\ge2$, and obtain an exact matching characterization for graphs of maximum degree at most three. Consequently every cubic graph of order $n$ satisfies $n/2\\le\\psq(G)\\le3n/5$, with a stability…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-20","reactions":{}}