no. 16 · Tuesday 17 November 2026
Elections, Fractional Dichromatic Number and Domination in Tournaments and Digraphs
Abstract
The dichromatic number of a digraph is the minimum number of induced acyclic sets into which its vertex set can be partitioned. The fractional dichromatic number is its fractional relaxation. Bourneuf, Charbit and Thomassé showed that the domination number of a tournament can be bounded as an (exponential) function of its fractional dichromatic number. This naturally leads to the question of finding a polynomial bound. We show that this bound is linear. To do this, we show a connection between undominated sets in elections and dominating sets in tournaments with bounded fractional dichromatic number. Within this framework, we also connect the well-known question of the existence of small Condorcet winning sets in elections to domination problems in digraphs with fractional dichromatic number less than 2. Thus, we open a new path to investigating these popular open problems in social choice from the perspective of graph theory.
- fields
- Combinatorics