We prove that every digraph has a vertex 4-colouring such that for each vertex v, at most half the out-neighbours of v receive the same colour as v. We then obtain several results related to the conjecture obtained by replacing 4 by 3.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics