Fractional majority colouring weight below 3

Open Problem 8 · arXiv:1608.03040

arXiv Problem high confidence— first stated 2016-08-10

Authors: Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, David R. Wood

Status partial high confidence

The minimum total weight k for fractional majority colourings of all digraphs remains unresolved below 3 in full generality. Anastos, Lamaison, Steiner, and Szabó (arXiv:1911.01954, EJC 2021) proved k ≤ 3.9602 for all digraphs (Theorem 6), and that digraphs with minimum out-degree Ω((1/ε)² ln(1/ε)) admit fractional majority (2+ε)-colourings (Theorem 7), placing dense digraphs below the conjectured threshold. The general question of whether k < 3 for every digraph remains open.

Cited literature (1)

partial Majority Colorings of Sparse Digraphs (2021)

Michael Anastos, Ander Lamaison, Raphael Steiner, Tibor Szabó · The Electronic Journal of Combinatorics · arXiv:1911.01954

Proves k ≤ 3.9602 for all digraphs (Theorem 6) and that digraphs with sufficiently large minimum out-degree admit fractional majority (2+ε)-colourings (Theorem 7), providing partial support for but not settling the conjecture that k < 3.

Reviewer notes. Open Problem 8 asks for the minimum total weight k over all fractional majority colourings of all digraphs, with the informal conjecture that k < 3. The best known upper bound is k ≤ 3.9602, established by arXiv:1911.01954 (Theorem 6). For dense digraphs with large minimum out-degree, k < 3 is confirmed. No paper published after 2021 specifically resolving this fractional problem was found in the indexed literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Let $S(G)$ be the set of all stable sets of a digraph $G$ and $S(G,v)$ the stable sets containing $v$. A fractional majority colouring assigns each $T \in S(G)$ a weight $x_T \geq 0$ such that $\sum_{T \in S(G,v)} x_T \geq 1$ for each vertex $v$. What is the minimum $k$ such that every digraph $G$ has a fractional majority colouring with $\sum_{T \in S(G)} x_T \leq k$? Perhaps $k < 3$.

Context

This fractional relaxation of majority colouring is introduced in Section 5 as a natural variant. The informal conjecture that the minimum total weight is less than 3 would constitute a fractional analogue of Conjecture 2.

Notes. The 'perhaps $k < 3$' is an informal conjectural remark embedded within the open problem statement.

Source paper

Majority Colourings of Digraphs
Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, David R. Wood · 2016-08-10
https://arxiv.org/abs/1608.03040 PDF source