TY - JOUR

T1 - Out-colourings of digraphs

AU - Alon, Noga

AU - Bang-Jensen, Jørgen

AU - Bessy, Stéphane

N1 - Funding Information:
This research was supported in part by NSF grant DMS‐1855464, ISF grant 281/17, GIF grant G‐1347‐304.6/2016 and the Simons Foundation. Financial support was received from the Danish research council, grant numbers 1323‐00178B and DFF‐7014‐00037B and the OSMO project, Occitanie regional council and DISCO project, PICS, CNRS. . Recall that NAE‐3‐SAT is the variant of 3‐SAT where we seek a truth assignment t such that each clause has both a false and a true literal under t . The further restriction monotone NAE‐3‐SAT means that we restrict to instances with no negated variables. This problem is still NP ‐complete

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.).

AB - 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.).

KW - Paley tournament

KW - degree constrained partitioning of digraphs

KW - out-colourings

KW - polynomial algorithm

KW - probabilistic method

KW - semicomplete digraphs

KW - tournaments

UR - http://www.scopus.com/inward/record.url?scp=85075119999&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075119999&partnerID=8YFLogxK

U2 - 10.1002/jgt.22476

DO - 10.1002/jgt.22476

M3 - Article

AN - SCOPUS:85075119999

VL - 93

SP - 88

EP - 112

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 1

ER -