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
Publisher Copyright:
© 2019 Wiley Periodicals, Inc.
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
SN - 0364-9024
VL - 93
SP - 88
EP - 112
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 1
ER -