{"id":"arxiv/2610.11997","url":"https://arxiv.org/abs/2610.11997","tags":["math.CO"],"score":0,"title":"Fractional majority coloring of digraphs: bounds and inapproximability","domain":"math.CO","source":"arxiv","authors":["Walid Ben-Ameur","Alessandro Maddaloni"],"reviews":0,"subject":"math.CO","summary":"A set of vertices in a digraph is majority-stable if each of its vertices has at most half of its outneighbors in the set. A fractional majority coloring assigns nonnegative weights to such sets, covering each vertex to total weight at least one; its minimum total weight is the fractional majority coloring number. We prove that every finite loopless digraph has fractional majority coloring number at most \\(523/140 0\\), we obtain a randomized \\((2.491+\\varepsilon)\\)-approximation algorithm producing an explicit fractional majority coloring in expected polynomial time. On the complexity side,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-08","reactions":{}}