Out-colourings of digraphs

Noga Alon, Jørgen Bang-Jensen, Stéphane Bessy

Research output: Contribution to journalArticlepeer-review

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 (Formula presented.) -complete. We show that for every choice of positive integers (Formula presented.) there exists a (Formula presented.) -strong bipartite tournament, which needs at least (Formula presented.) colours in every out-colouring. Our main results are on tournaments and semicomplete digraphs. We prove that, except for the Paley tournament (Formula presented.), 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 (Formula presented.) of a digraph (Formula presented.) so that each of the three digraphs induced by respectively, the vertices of (Formula presented.), the vertices of (Formula presented.) and all arcs between (Formula presented.) and (Formula presented.), have minimum out-degree (Formula presented.) for a prescribed integer (Formula presented.). Using probabilistic arguments, we prove that there exists an absolute positive constant (Formula presented.) so that every semicomplete digraph of minimum out-degree at least (Formula presented.) has such a partition. This is tight up to the value of (Formula presented.).

Original languageEnglish (US)
Pages (from-to)88-112
Number of pages25
JournalJournal of Graph Theory
Volume93
Issue number1
DOIs
StatePublished - Jan 1 2020

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Paley tournament
  • degree constrained partitioning of digraphs
  • out-colourings
  • polynomial algorithm
  • probabilistic method
  • semicomplete digraphs
  • tournaments

Fingerprint Dive into the research topics of 'Out-colourings of digraphs'. Together they form a unique fingerprint.

Cite this