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 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 (V1,V2) of a digraph D so that each of the three digraphs induced by respectively, 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+ck has such a partition. This is tight up to the value of c. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1002/jgt.22476 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
degree constrained partitioning of digraphs,out-colourings,Paley tournament,polynomial algorithm,probabilistic method,semicomplete digraphs,tournaments | Journal | 93.0 |
Issue | ISSN | Citations |
1.0 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Noga Alon | 1 | 10468 | 1688.16 |
Jørgen Bang-Jensen | 2 | 573 | 68.96 |
Stéphane Bessy | 3 | 117 | 19.68 |