Skip to Main content Skip to Navigation
Journal articles

Out‐colourings of digraphs

Abstract : 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 P7, every strong semicomplete digraph of minimum out-degree at least 3 has a 2-out-colouring. Furthermore, we show that every semi- complete digraph on at least 7 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 (V1,V2) of a digraph D so that each of the three digraphs induced by re- spectively, the vertices of V1, the vertices of V2 and all arcs between V1 and V2 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 2k + c k has such a partition. This is tight up to the value of c.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03271566
Contributor : Stéphane Bessy Connect in order to contact the contributor
Submitted on : Saturday, June 26, 2021 - 7:06:14 AM
Last modification on : Friday, October 22, 2021 - 3:07:30 PM

Links full text

Identifiers

Collections

Citation

Noga Alon, Jørgen Bang‐jensen, Stéphane Bessy. Out‐colourings of digraphs. Journal of Graph Theory, Wiley, 2020, 93 (1), pp.88-112. ⟨10.1002/jgt.22476⟩. ⟨lirmm-03271566⟩

Share

Metrics

Record views

20