\documentclass[12pt]{article} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{amsthm,amsmath} \usepackage[noabbrev,capitalise]{cleveref} \usepackage{e-jc} \specs{P2.25}{24(2)}{2017} %\usepackage{amsthm,amsmath} %\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage[numbers,sort&compress]{natbib} \setlength{\bibsep}{0.4ex plus 0.1ex minus 0.1ex} \theoremstyle{plain} \newtheorem{thm}{Theorem} \newtheorem{lem}[thm]{Lemma} \newtheorem{conj}[thm]{Conjecture} \newtheorem{cor}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} %\usepackage[noabbrev,capitalise]{cleveref} \crefname{lem}{Lemma}{Lemmas} \crefname{thm}{Theorem}{Theorems} \crefname{prop}{Proposition}{Propositions} \crefname{conj}{Conjecture}{Conjectures} \newcommand{\arXiv}[1]{\texttt{arXiv:}\,\href{http://arxiv.org/abs/#1}{#1}} \newcommand{\msn}[1]{MR:\,\href{http://www.ams.org/mathscinet-getitem?mr=MR#1}{#1}} \newcommand{\doi}[2]{\href{http://dx.doi.org/#1}{#2}} \newcommand{\FLOOR}[1]{\ensuremath{\protect\left\lfloor#1\right\rfloor}} \newcommand{\CEIL}[1]{\ensuremath{\protect\left\lceil#1\right\rceil}} \newcommand{\ceil}[1]{\lceil{#1}\rceil} \newcommand{\floor}[1]{\lfloor{#1}\rfloor} \renewcommand{\geq}{\geqslant} \renewcommand{\leq}{\leqslant} \renewcommand{\thefootnote}{\fnsymbol{footnote}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf Majority Colourings of Digraphs} \author{ Stephan Kreutzer\,\footnotemark[2] \quad Sang-il Oum\,\footnotemark[3] \quad Paul Seymour\,\footnotemark[4] \\ Dominic van der Zypen\,\footnotemark[5] \quad David~R.~Wood\,\footnotemark[6] } \date{\dateline{Aug 26, 2016}{May 3, 2017}{May 19, 2017}\\ \small Mathematics Subject Classifications: 05C15, 05C20} \begin{document} \maketitle \begin{abstract} We prove that every digraph has a vertex 4-colouring such that for each vertex $v$, at most half the out-neighbours of $v$ receive the same colour as $v$. We then obtain several results related to the conjecture obtained by replacing 4 by 3. \end{abstract} \footnotetext[2]{Chair for Logic and Semantics, Technical University Berlin, Germany (\texttt{stephan.kreutzer@tu-berlin.de}). Research partly supported by DFG Emmy-Noether Grant Games and by the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No 648527).} \footnotetext[3]{Department of Mathematical Sciences, KAIST, Daejeon, South Korea (\texttt{sangil@kaist.edu}).} \footnotetext[4]{Department of Mathematics, Princeton University, New Jersey, U.S.A. (\texttt{pds@math.princeton.edu}).} \footnotetext[5]{Federal Office of Social Insurance, Bern, Switzerland (\texttt{dominic.zypen@gmail.com}).} \footnotetext[6]{School of Mathematical Sciences, Monash University, Melbourne, Australia (\texttt{david.wood@monash.edu}). Research supported by the Australian Research Council.} \renewcommand{\thefootnote}{\arabic{footnote}} %%%%%%%%%%%%%%%%% \section{Introduction} \label{Intro} A \emph{majority colouring} of a digraph is a function that assigns each vertex $v$ a colour, such that at most half the out-neighbours of $v$ receive the same colour as $v$. In other words, at least half the out-neighbours of $v$ receive a colour different from $v$ (hence the name `majority'). Whether every digraph has a majority colouring with a bounded number of colours was posed as an open problem on mathoverflow \citep{Zypen-mathoverflow}. In response, Ilya Bogdanov proved that a bounded number of colours suffice for tournaments. The following is our main result. \begin{thm} \label{4Colouring} Every digraph has a majority 4-colouring. \end{thm} \begin{proof} Fix a vertex ordering. First, 2-colour the vertices left-to-right so that for each vertex $v$, at most half the out-neighbours of $v$ to the left of $v$ in the ordering receive the same colour as $v$. Second, 2-colour the vertices right-to-left so that for each vertex $v$, at most half the out-neighbours of $v$ to the right of $v$ in the ordering receive the same colour as $v$. The product colouring is a majority 4-colouring. \end{proof} Note that this proof implicitly uses two facts: (1) every digraph has an edge-partition into two acyclic subgraphs, and (2) every acyclic digraph has a majority 2-colouring. The following conjecture naturally arises: \begin{conj} \label{Main} Every digraph has a majority 3-colouring. \end{conj} This conjecture would be best possible. For example, a majority colouring of an odd directed cycle is proper (since each vertex has out-degree 1), and therefore three colours are necessary. There are examples with large minimum out-degree as well. For odd $k\geq 1$ and prime $n\gg k$, let $G$ be the directed graph with $V(G)=\{v_0,\dots,v_{n-1}\}$ where $N_G^+(v_i)=\{v_{i+1},\dots,v_{i+k}\}$ and vertex indices are taken modulo $n$. Suppose that $G$ has a majority 2-colouring. If some sequence $v_i,v_{i+1},\dots,v_{i+k}$ contains more than $\frac{k+1}{2}$ vertices of one colour, say red, and $v_i$ is the leftmost red vertex in this sequence, then more than $\frac{k-1}{2}$ out-neighbours of $v_i$ are red, which is not allowed. Thus each sequence $v_i,v_{i+1},\dots,v_{i+k}$ contains exactly $\frac{k+1}{2}$ vertices of each colour. This implies that $v_i$ and $v_{i+k+1}$ receive the same colour, as otherwise the sequence $v_{i+1},\dots,v_{i+k+1}$ would contain more than $\frac{k+1}{2}$ vertices of the colour assigned to $v_{i+k+1}$. For all vertices $v_i$ and $v_j$, if $\ell=\frac{j-i}{k+1}$ in the finite field $\mathbb{Z}_n$, then $j=i+\ell(k+1)$ and $v_i,v_{i+(k+1)},v_{i+2(k+1)},\dots,v_{i+\ell(k+1)}=v_j$ all receive the same colour. Thus all the vertices receive the same colour, which is a contradiction. Hence the claimed 2-colouring does not exist. Note that being majority $c$-colourable is not closed under taking induced subgraphs. For example, let $G$ be the digraph with $V(G)=\{a,b,c,d\}$ and $E(G)=\{ab,bc,ca,cd\}$. Then $G$ has a majority 2-colouring: colour $a$ and $c$ by $1$ and colour $b$ and $d$ by $2$. But the subdigraph induced by $\{a,b,c\}$ is a directed 3-cycle, which has no majority 2-colouring. The remainder of the paper takes a probabilistic approach to \cref{Main}, proving several results that provide evidence for \cref{Main}. A probabilistic approach is reasonable, since in a random 3-colouring, one would expect that a third of the out-neighbours of each vertex $v$ receive the same colour as $v$. So one might hope that there is enough slack to prove that for \emph{every} vertex $v$, at most half the out-neighbours of $v$ receive the same colour as $v$. \cref{LargeOutdegree} proves \cref{Main} for digraphs with very large minimum out-degree (at least logarithmic in the number of vertcies), and then for digraphs with large minimum out-degree (at least a constant) and not extremely large maximum in-degree. \cref{IndependentSets} shows that large minimum out-degree (at least a constant) is sufficient to prove the existence of one of the colour classes in \cref{Main}. \cref{Generalisation} discusses multi-colour generalisations of \cref{Main}. Before proceeding, we mention some related topics in the literature: \begin{itemize} \item For undirected graphs, the situation is much simpler. \citet{Lovasz66} proved that for every undirected graph $G$ and integer $k\geq 1$, there is a $k$-colouring of $G$ such that every vertex $v$ has at most $\frac{1}{k}\deg(v)$ neighbours receiving the same colour as $v$. The proof is simple. Consider a $k$-colouring of $G$ that minimises the number of monochromatic edges. Suppose that some vertex $v$ coloured $i$ has greater than $\frac{1}{k} \deg(v)$ neighbours coloured $i$. Thus less than $\frac{k-1}{k}\deg(v)$ neighbours of $v$ are not coloured $i$, and less than $\frac{1}{k}\deg(v)$ neighbours of $v$ receive some colour $j\neq i$. Thus, if $v$ is recoloured $j$, then the number of monochromatic edges decreases. Hence no vertex $v$ has greater than $\frac{1}{k}\deg(v)$ neighbours with the same colour as $v$. \item \citet{Seymour74} considered digraph colourings such that every non-sink vertex receives a colour different from some outneighbour, and proved that a strongly-connected digraph $G$ admits a 2-colouring with this property if and only if $G$ has an even directed cycle. The proof shows that every digraph has such a 3-colouring, which we repeat here: We may assume that $G$ is strongly connected. In particular, there are no sink vertices. Choose a maximal set $X$ of vertices such that $G[X]$ admits a 3-colouring where every vertex has a colour different from some outneighbour. Since any directed cycle admits such a colouring, $X\neq\emptyset$. If $X \neq V(G)$, then choose an edge $uv$ entering $X$ and colour $u$ different from the colour of $v$, contradicting the maximality of $X$. So $X=V(G)$. (The same proof shows two colours suffice if you start with an even cycle.)\ \item \citet{Alon96a,Alon06} posed the following problem: Is there a constant $c$ such that every digraph with minimum out-degree at least $c$ can be vertex-partitioned into two induced digraphs, one with minimum out-degree at least 2, and the other with minimum out-degree at least 1? \item \citet{Wood-JCTB04} proved the following edge-colouring variant of majority colourings: For every digraph $G$ and integer $k\geq 2$, there is a partition of $E(G)$ into $k$ acyclic subgraphs such that each vertex $v$ of $G$ has out-degree at most $\ceil{\frac{\deg^+(v)}{k-1}}$ in each subgraph. The bound $\ceil{\frac{\deg^+(v)}{k-1}}$ is best possible, since in each acyclic subgraph at least one vertex has out-degree 0. \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%% \section{Large Outdegree} \label{LargeOutdegree} We now show that minimum out-degree at least logarithmic in the number of vertices is sufficient to guarantee a majority 3-colouring. All logarithms are natural. \begin{thm} \label{LogarithmicOutdegree} Every $n$-vertex graph $G$ with minimum out-degree $\delta> 72\log(3n)$ has a majority 3-colouring. Moreover, at most half the out-neighbours of each vertex receive the same colour. \end{thm} \begin{proof} Randomly and independently colour each vertex of $G$ with one of three colours $\{1, 2, 3\}$. Consider a vertex $v$ with out-degree $d_v$. Let $X(v,c)$ be the random variable that counts the number of out-neighbours of $v$ coloured $c$. Of course, $\mathbf{E}(X(v,c)) = d_v/3$. Let $A(v,c)$ be the event that $X(v,c) > d_v/2$. Note that $X(v,c)$ is determined by $d_v$ independent trials and changing the outcome of any one trial changes $X(v,c)$ by at most~1. By the simple concentration bound\footnote{The simple concentration bound says that if $X$ is a random variable determined by $d$ independent trials, such that changing the outcome of any one trial can affect $X$ by at most $c$, then $\textbf{P}(X >\textbf{E}(X) + t) \leq \exp(-t^2/2c^2d)$; see \citep[Chapter 10]{MR02}. With $\textbf{E}(X_v)=d_v/3$ and $t=d_v/6$ and $c=1$ we obtain the desired upper bound on $\textbf{P}(X_v > d_v/2)$.}, \begin{align*} \mathbf{P}(A(v, c)) \leq \exp(-(d_v/6)^2/2d_v) = \exp(-d_v/72) \leq \exp(-\delta/72). \end{align*} The expected number of events $A(v,c)$ that hold is $$\sum_{v\in V(G)}\sum_{c\in \{1,2,3\}}\mathbf{P}(A(v, c)) \leq 3n \exp(-\delta/72)<1,$$ where the last inequality holds since $\delta> 72\log(3n)$. Thus there exist colour choices such that no event $A(v,c)$ holds. That is, a majority 3-colouring exists. \end{proof} The following result shows that large out-degree (at least a constant) and not extremely large in-degree is sufficient to guarantee a majority 3-colouring. \begin{thm} \label{LocalLemmaColouring} Every digraph $G$ with minimum out-degree $\delta\geq 1200$ and maximum in-degree at most $\exp(\delta/72)/12\delta$ has a majority 3-colouring. Moreover, at most half the out-neighbours of each vertex receive the same colour. \end{thm} \begin{proof} We assume $\delta\geq 1200$, as otherwise the minimum out-degree $\delta$ is greater than the maximum in-degree $\exp(\delta/72)/12\delta$, which does not make sense. We use the following weighted version of the Local Lemma \citep{EL75,MR02}:\,Let $\mathcal{A} := \{A_1, \dots, A_n\}$ be a set of `bad' events, such that each $A_i$ is mutually independent of $\mathcal{A}\setminus (D_i \cup \{A_i\})$, for some subset $D_i \subseteq A$. Assume there are numbers $t_1,\dots,t_n \geq 1$ and a real number $p \in [0, \frac14]$ such that for $1 \leq i \leq n$, $$(a)\; \mathbf{P}(A_i) \leq p^{t_i} \quad \text{and} \quad (b)\; \sum_{A_j\in \mathcal{D}_i} (2p)^{t_j} \leq t_i/2.$$ Then with positive probability no event $A_i$ occurs. Define $p := \exp(-\delta /72)$. Since $\delta \geq1200$ we have $p\in [0, \frac14]$. Randomly and independently colour each vertex of $G$ with one of three colours $\{1, 2, 3\}$. Consider a vertex $v$ with out-degree $d_v$. Let $X(v,c)$ be the random variable that counts the number of out-neighbours of $v$ coloured $c$. Of course, $\mathbf{E}(X(v,c)) = d_v/3$. Let $A(v,c)$ be the event that $X(v,c) > d_v/2$. Let $\mathcal{A} := \{A(v,c) : v \in V(G),c \in \{1,2,3\}\}$ be our set of events. Let $t(v,c) := t_v := d_v/\delta$ be the associated weight. Then $t_v \geq 1$. It suffices to prove that conditions (a) and (b) hold. Note that $X(v,c)$ is determined by $d_v$ independent trials and changing the outcome of any one trial changes $X(v,c)$ by at most 1. By the simple concentration bound, \begin{align*} \mathbf{P}(A(v, c)) \leq \exp(-(d_v/6)^2/2d_v) = \exp(-d_v/72) = \exp(-\delta t_v/72) = p^{t_v}. \end{align*} Thus condition (a) is satisfied. For each event $A(v,c)$ let $D(v,c)$ be the set of all events $A(w,c') \in \mathcal{A}$ such that $v$ and $w$ have a common out-neighbour. Then $A(v, c)$ is mutually independent of $\mathcal{A} \setminus (D(v, c) \cup \{A(v, c)\})$. Since $t_w \geq 1$, \begin{align*} \sum_{A(w,c')\in D(v,c)}\!\!\!\!\!\!\!\! (2p)^{t_w} \leq \sum_{A(w,c')\in D(v,c)}\!\!\!\!\!\!\!\! (2p)^1 = 2p |D(v, c)|. \end{align*} Since each out-neighbour of $v$ has in-degree at most $\exp(\delta /72)/12\delta$, we have $|D(v,c)| \leq d_v\exp(\delta /72)/4\delta$ and \begin{align*} \sum_{A(w,c')\in D(v,c)} (2p)^{t_w} \leq p d_v \exp(\delta/72)/2\delta = \exp(-\delta/72) t_v \exp(\delta/72)/2 = t_v/2. \end{align*} Thus condition (b) is satisfied. By the local lemma, with positive probability, no event $A(v,c)$ occurs. That is, a majority 3-colouring exists. \end{proof} Note that the conclusion in \cref{LogarithmicOutdegree,LocalLemmaColouring} is stronger than in Conjecture~\ref{Main}. We now show that such a conclusion is impossible (without some extra degree assumption). \begin{lem} For all integers $k$ and $\delta$, there are infinitely many digraphs $G$ with minimum out-degree $\delta$, such that for every vertex $k$-colouring of $G$, there is a vertex $v$ such that all the out-neighbours of $v$ receive the same colour. \end{lem} \begin{proof} Start with a digraph $G_0$ with at least $k\delta$ vertices and minimum out-degree $\delta$. For each set $S$ of $\delta$ vertices in $G_0$, add a new vertex with out-neighbourhood $S$. Let $G$ be the digraph obtained. In every $k$-colouring of $G$, at least $\delta$ vertices in $G_0$ receive the same colour, which implies that for some vertex $v\in V(G)\setminus V(G_0)$, all the out-neighbours of $v$ receive the same colour. \end{proof} %%%%%% \section{Stable Sets} \label{IndependentSets} A set $T$ of vertices in a digraph $G$ is a \emph{stable set} if for each vertex $v\in T$, at most half the out-neighbours of $v$ are also in $T$. A majority colouring is a partition into stable sets. Of course, if a digraph has a majority 3-colouring, then it contains a stable set with at least one third of the vertices. The next lemma provides a sufficient condition for the existence of such a set. \begin{thm} \label{IndSet} Every $n$-vertex digraph $G$ with minimum out-degree at least $22$ has a stable set with at least $\frac{n}{3}$ vertices. \end{thm} \cref{IndSet} is proved via the following more general lemma. \begin{lem} \label{GenIndSet} For $0<\alpha \beta d_v) = \sum_{k\geq\floor{\beta d_v}+1}^{d_v} \binom{d_v}{k} p^k (1-p)^{d_v-k}. \end{equation} By the Chernoff bound\footnote{The Chernoff bound implies that if $X\sim\text{Bin}(d,p)$ then $\textbf{P}(X\geq (1+\epsilon)pd) \leq \exp( - \frac{\epsilon^2}{2+\epsilon}\, pd)$ for $\epsilon\geq 0$. With $\epsilon=\frac{\beta}{p}-1$ we have $\textbf{P}(X> \beta d) \leq \exp( - \frac{(\beta-p)^2}{p+\beta}\, d)$.}, \begin{equation} \label{PXvdesired} \mathbf{P}(X_v > \beta d_v) \leq \exp\left( - \frac{(\beta-p)^2}{\beta+p} d_v \right) \leq \exp\left( - \frac{(\beta-p)^2}{\beta+p} \delta \right) \leq \frac{p-\alpha}{p}, \end{equation} where the last inequality follows from the definition of $\delta$. Let $B:=\{v\in S:X_v > \beta d_v\}$. Then \begin{align*} \mathbf{E}(|B|) = \sum_{v\in V(G)} \mathbf{P}( v\in S \text{ and }X_v > \beta d_v). \end{align*} Since the events $v\in S$ and $X_v > \beta d_v$ are independent, \begin{align*} \mathbf{E}(|B|) = \sum_{v\in V(G)} \mathbf{P}( v\in S ) \,\mathbf{P}(X_v > \beta d_v) = p \sum_{v\in V(G)} \mathbf{P}(X_v > \beta d_v) \leq (p-\alpha)n. \end{align*} Let $T:=S\setminus B$. Thus $|N^+_G(v)\cap T| \leq \beta d_v$ for each vertex $v\in T$, as desired. By the linearity of expectation, $$\mathbf{E}(|T|)=\mathbf{E}(|S|)-\mathbf{E}(|B|)=pn-\mathbf{E}(|B|) \geq \alpha n.$$ Thus the desired set $T$ exists. \end{proof} \begin{proof}[Proof of \cref{IndSet}] The proof follows that of \cref{GenIndSet} with one change. Let $\alpha:=\frac13$ and $\beta:=\frac12$ and $p:=0.38$. Then $\delta=129$. If $22\leq d_v\leq 128$ then direct calculation of the formula in \eqref{PXv} verifies that $\mathbf{P}(X_v > \beta d_v) \leq \frac{p-\alpha}{p}$, as in \eqref{PXvdesired}. For $d_v\geq 129$ the Chernoff bound proves \eqref{PXvdesired}. The rest of the proof is the same as in \cref{GenIndSet}. \end{proof} Note the following corollary of \cref{GenIndSet} obtained with $\alpha=\frac12-\epsilon$ and $p=\frac12-\frac{\epsilon}{2}$. This says that graphs with large minimum out-degree have a stable set with close to half the vertices. \begin{prop} For $0<\epsilon<\frac12$, every $n$-vertex digraph $G$ with minimum out-degree at least $2\epsilon^{-2}(2-\epsilon) \log(\tfrac{1-\epsilon}{\epsilon})$ contains a stable set of at least $(\frac12-\epsilon)n$ vertices. \end{prop} %%%%%%%%%%%%%%%%%%%%%%%% \section{Multi-Colour Generalisation} \label{Generalisation} In the initial version of this paper we suggested the following natural generalisation of \cref{Main}: \begin{conj} \label{kColours} For $k\geq 2$, every digraph has a vertex $(k+1)$-colouring such that for each vertex $v$, at most $\frac{1}{k}\deg^+(v)$ out-neighbours of $v$ receive the same colour as $v$. \end{conj} Gregory Gauthier [personal communication, Banff workshop ``New Trends in Graph Coloring'', October 2016] and independently \citet{GKP17} observed that this conjecture is false, as shown by the cyclic orientation of $K_{2c-1}$, which has out-degree $c- 1$ at every vertex, and thus all vertices receive distinct colors. Because of this example, we wonder if \cref{kColours} holds if every vertex has out-degree at least $c$, which is a natural assumption in this context. Without this extra assumption, the following conjecture would be best possible by the above example. \begin{conj} \label{kColoursNew} For $k\geq 2$, every digraph has a vertex $(2k-1)$-colouring such that for each vertex $v$, at most $\frac{1}{k}\deg^+(v)$ out-neighbours of $v$ receive the same colour as $v$. \end{conj} This conjecture would be best possible by the above example. The proof of \cref{4Colouring} generalises to give an upper bound of $k^2$ on the number of colours in \cref{kColours,kColoursNew}. It is open whether the number of colours is $O(k)$. \cref{GenIndSet} with $\alpha=\frac{1}{k}-\epsilon$ and $\beta=\frac{1}{k}$ and $p=\frac{1}{k}-\frac{\epsilon}{2}$ implies the following `stable set' version of \cref{kColours} for digraphs with large minimum out-degree. \begin{prop} \label{kIndSet} For $k\geq 2$ and $\epsilon\in(0,\frac{1}{k})$, every $n$-vertex digraph $G$ with minimum out-degree at least $2\epsilon^{-2} (\tfrac{4}{k}-\epsilon) \log\left(\tfrac{2}{\epsilon k}-1\right)$ contains a set $T$ of at least $(\frac{1}{k}-\epsilon)n$ vertices, such that for every vertex $v\in T$, at most $\frac{1}{k}\deg^+(v)$ out-neighbours of $v$ are also in $T$. \end{prop} \section{Open Problems} In addition to resolving \cref{Main}, the following open problems arise from this paper: \begin{enumerate} \item \label{Weak3Colour} Is there a constant $\beta<1$ for which every digraph has a 3-colouring, such that for every vertex $v$, at most $\beta\deg^+(v)$ out-neighbours receive the same colour as $v$? \item \label{Tournament} Does every tournament have a majority 3-colouring? \item\label{Eulerian} Does every Eulerian digraph have a majority 3-colouring? Note that for an Eulerian digraph $G$, if each vertex $v$ has in-degree and out-degree $\deg(v)$, then by the result for undirected graphs mentioned in \cref{Intro}, the underlying undirected graph of $G$ has a 4-colouring such that each vertex $v$ has at most $\frac{1}{2}\deg(v)$ in- or- out-neighbours with the same colour as $v$. In particular, $G$ has a majority 4-colouring. By an analogous argument every Eulerian digraph has a 3-colouring such that each vertex $v$ has at most $\frac{2}{3}\deg(v)$ in- or- out-neighbours with the same colour as $v$, thus proving a special case of the first question above. \item \label{InOut} Does every digraph in which every vertex has in-degree and out-degree $k$ have a majority 3-colouring? A variant of \cref{LocalLemmaColouring} proves this result for $k\geq 144$. \item \label{2Colouring} Is there a characterisation of digraphs that have a majority 2-colouring (or a polynomial time algorithm to recognise such digraphs)? \item \label{Linear} Does every digraph have a $O(k)$-colouring such that for each vertex $v$, at most $\frac{1}{k}\deg^+(v)$ out-neighbours receive the same colour as $v$ (for all $k\geq 2$)? \item \label{Choosable} A digraph $G$ is \emph{majority $c$-choosable} if for every function $L:V(G)\rightarrow\mathbb{Z}$ with $|L(v)|\geq c$ for each vertex $v\in V(G)$, there is a majority colouring of $G$ with each vertex $v$ coloured from $L(v)$. Is every digraph majority $c$-choosable for some constant $c$? The proof of \cref{4Colouring} shows that acyclic digraphs are majority 2-choosable, and obviously \cref{LogarithmicOutdegree} and \cref{LocalLemmaColouring} extend to the setting of choosability. \item \label{Fractional} Consider the following fractional setting. Let $S(G)$ be the set of all stable sets of a digraph $G$. Let $S(G,v)$ be the set of all stable sets containing $v$. A \emph{fractional majority colouring} is a function that assigns each stable set $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$ of $G$. What is the minimum number $k$ such that every digraph $G$ has a fractional majority colouring with total weight $\sum_{T\in S(G)}x_T\leq k$? \end{enumerate} %%%%%%%%%%%%% \section{Update} Since this paper was submitted there has been significant progress on several of the above open problems. Question~\ref{Weak3Colour} was answered by \citet{ABG16} with $\beta=\frac23$. More generally, \citet{GKP17} and \citet{KS17} proved that for $k\geq 2$ every digraph has a $k$-colouring such that for each vertex $v$, at most $\frac{2}{k}\deg^+(v)$ out-neighbours of $v$ receive the same colour as $v$. This answers Question~\ref{Linear} and answers Question~\ref{Weak3Colour} with $\beta=\frac23$. Question~\ref{Tournament} was partially answered by \citet{GKP17}. They proved that every tournament with minimum out-degree at least 50 is majority 3-colourable, and that every tournament can be 3-coloured so that all but at most 7 vertices receive the same colour as at most half of their out-neighbours. Question~\ref{Choosable} was answered by \citet{ABG16}, \citet{GKP17} and \citet{KS17} who all proved that every digraph is majority $4$-choosable. Moreover, the above results concerning Questions~\ref{Weak3Colour} and \ref{Linear} were established in the choosability setting. %%%%%%%%%%%% \subsection*{Acknowledgements} This research was initiated at the Workshop on Graph Theory at Bellairs Research Institute (March 25 -- April 1, 2016). %\bibliographystyle{plainnat} %\bibliography{myBibliography} \def\soft#1{\leavevmode\setbox0=\hbox{h}\dimen7=\ht0\advance \dimen7 by-1ex\relax\if t#1\relax\rlap{\raise.6\dimen7 \hbox{\kern.3ex\char'47}}#1\relax\else\if T#1\relax \rlap{\raise.5\dimen7\hbox{\kern1.3ex\char'47}}#1\relax \else\if d#1\relax\rlap{\raise.5\dimen7\hbox{\kern.9ex \char'47}}#1\relax\else\if D#1\relax\rlap{\raise.5\dimen7 \hbox{\kern1.4ex\char'47}}#1\relax\else\if l#1\relax \rlap{\raise.5\dimen7\hbox{\kern.4ex\char'47}}#1\relax \else\if L#1\relax\rlap{\raise.5\dimen7\hbox{\kern.7ex \char'47}}#1\relax\else\message{accent \string\soft \space #1 not defined!}#1\relax\fi\fi\fi\fi\fi\fi} \begin{thebibliography}{11} \providecommand{\natexlab}[1]{#1} %\providecommand{\url}[1]{\texttt{#1}} \bibitem[Alon(1996)]{Alon96a} Noga Alon. \newblock \doi{10.1006/jctb.1996.0062}{Disjoint directed cycles}. \newblock \emph{J. Combin. Theory Ser. B}, 68\penalty0 (2):\penalty0 167--178, 1996. \msn{1417794}. \bibitem[Alon(2006)]{Alon06} Noga Alon. \newblock \doi{10.1017/S0963548306008042}{Splitting digraphs}. \newblock \emph{Combin. Probab. Comput.}, 15\penalty0 (6):\penalty0 933--937, 2006. \msn{2271836}. \bibitem[Anholcer et~al.(2016)Anholcer, Bosek, and Grytczuk]{ABG16} Marcin Anholcer, Bart{\l}omiej Bosek, and Jaros{\l}aw Grytczuk. \newblock Majority choosability of digraphs, 2016. \newblock \arXiv{1608.06912}. \bibitem[Erd{\H{o}}s and Lov\'{a}sz(1975)]{EL75} Paul Erd{\H{o}}s and L\'{a}szl\'{o} Lov\'{a}sz. \newblock \href{https://www.renyi.hu/~p_erdos/1975-34.pdf}{Problems and results on {$3$}-chromatic hypergraphs and some related questions}. \newblock In \emph{Infinite and Finite Sets}, volume~10 of \emph{Colloq. Math. Soc. J\'anos Bolyai}, pages 609--627. North-Holland, 1975. \bibitem[Gir{\~a}o et~al.(2017)Gir{\~a}o, Kittipassorn, and Popielarz]{GKP17} Ant\'onio Gir{\~a}o, Teeradej Kittipassorn, and Kamil Popielarz. \newblock Generalised majority colourings of digraphs, 2017. \newblock \arXiv{1701.03780}. \bibitem[Knox and {\v{S}}{\'a}mal(2017)]{KS17} Fiachra Knox and Robert {\v{S}}{\'a}mal. \newblock Linear bound for majority colourings of digraphs, 2017. \newblock \arXiv{1701.05715}. \bibitem[Lov\'{a}sz(1966)]{Lovasz66} L\'{a}szl\'{o} Lov\'{a}sz. \newblock On decomposition of graphs. \newblock \emph{Studia Sci. Math. Hungar.}, 1:\penalty0 237--238, 1966. \newblock \msn{0202630}. \bibitem[Molloy and Reed(2002)]{MR02} Michael Molloy and Bruce Reed. \newblock \emph{Graph colouring and the probabilistic method}, volume~23 of \emph{Algorithms and Combinatorics}. \newblock Springer, 2002. \bibitem[Seymour(1974)]{Seymour74} Paul~D. Seymour. \newblock \doi{10.1093/qmath/25.1.303}{On the two-colouring of hypergraphs}. \newblock \emph{Quarterly J. Math}, 25\penalty0 (1):\penalty0 303--311, 1974. \msn{0371710}. \bibitem[van~der Zypen(2016)]{Zypen-mathoverflow} Dominic van~der Zypen. \newblock Majority coloring for directed graphs, 2016. \newblock \texttt{mathoverflow:}\href{http://mathoverflow.net/questions/233014/majority-coloring-for-directed-graphs}{233014}. \bibitem[Wood(2004)]{Wood-JCTB04} David~R. Wood. \newblock \doi{10.1016/j.jctb.2003.08.004}{Bounded degree acyclic decompositions of digraphs}. \newblock \emph{J. Combin. Theory Ser. B}, 90:\penalty0 309--313, 2004. \msn{2034031}. \end{thebibliography} \end{document}