, Assume that some terminal component, Q , in D is a k-regular tournament
, this implies that Q is also a terminal component in D, a contradiction Therefore no terminal component in D is a k-regular tournament and by induction there is a k-all-out-degreereducing 2k-partition of D . Now add w to a different part to all of its at most 2k ? 1 neighbours in G. This gives a k-all-out-degree-reducing 2k-partition of D
, the graph G is not an odd cycle. Therefore, by Brook's Theorem, G admits a proper 2k-colouring. This 2k-colouring gives us the desired k-all-out-degree-reducing 2k-partition of D
, Digraphs: Theory, Algorithms and Applications, 2009.
, Finding good 2-partitions of digraphs I. Hereditary properties, Theoretical Computer Science, vol.636, pp.85-94, 2016.
DOI : 10.1016/j.tcs.2016.05.029
URL : https://hal.archives-ouvertes.fr/hal-01327015
, Some connections between set theory and computer science, Proceedings Lecture Notes in Computer Science, vol.713, pp.14-22, 1993.
DOI : 10.1007/BFb0022548
, Majority colourings of digraphs, Electronic J. Combinatorics, vol.24, 2017.
, Permanents, Pfaffian Orientations, and Even Directed Circuits, The Annals of Mathematics, vol.150, issue.3, pp.929-975, 1999.
DOI : 10.2307/121059
URL : http://arxiv.org/pdf/math/9911268
, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, pp.216-226, 1978.
DOI : 10.1145/800133.804350
, ON THE TWO-COLOURING OF HYPERGRAPHS, The Quarterly Journal of Mathematics, vol.25, issue.1, pp.303-311, 1974.
DOI : 10.1093/qmath/25.1.303
, Even Cycles in Directed Graphs, European Journal of Combinatorics, vol.6, issue.1, pp.85-89, 1985.
DOI : 10.1016/S0195-6698(85)80025-1
, The even cycle problem for directed graphs, Journal of the American Mathematical Society, vol.5, issue.2, pp.217-229, 1992.
DOI : 10.1090/S0894-0347-1992-1135027-1