Premium
Out‐colourings of digraphs
Author(s) -
Alon Noga,
BangJensen Jørgen,
Bessy Stéphane
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22476
Subject(s) - combinatorics , tournament , mathematics , digraph , vertex (graph theory) , partition (number theory) , neighbourhood (mathematics) , degree (music) , discrete mathematics , bipartite graph , graph , mathematical analysis , physics , acoustics
We study vertex colourings of digraphs so that no out‐neighbourhood is monochromatic and call such a colouring an out‐colouring. The problem of deciding whether a given digraph has an out‐colouring with only two colours (called a 2‐out‐colouring) is NP ‐complete. We show that for every choice of positive integers r , k there exists a k ‐strong bipartite tournament, which needs at least r colours in every out‐colouring. Our main results are on tournaments and semicomplete digraphs. We prove that, except for the Paley tournament P 7 , every strong semicomplete digraph of minimum out‐degree at least three has a 2‐out‐colouring. Furthermore, we show that every semicomplete digraph on at least seven vertices has a 2‐out‐colouring if and only if it has a balanced such colouring, that is, the difference between the number of vertices that receive colour 1 and colour 2 is at most one. In the second half of the paper, we consider the generalization of 2‐out‐colourings to vertex partitions ( V 1 , V 2 ) of a digraph D so that each of the three digraphs induced by respectively, the vertices of V 1 , the vertices of V 2 and all arcs between V 1 and V 2 , have minimum out‐degree k for a prescribed integer k ≥ 1 . Using probabilistic arguments, we prove that there exists an absolute positive constant c so that every semicomplete digraph of minimum out‐degree at least 2 k + c k has such a partition. This is tight up to the value of c .