Uniquely colourable m-dichromatic oriented graphs (Q1088673)

The dichromatic number \(d_ k(D)\) of a digraph D is the minimum number of colours needed to colour V(D) in such a way that no monochromatic directed cycle is obtained. A digraph D is called uniquely colourable if any acyclic \(d_ k(D)\)-colouring of V(D) induces the same partition of V(D). The authors construct an infinite family of uniquely colourable m- dichromatic oriented graphs for all \(m\geq 2\). They give first of all two families of uniquely colourable 2-dichromatic oriented graphs \(\{H_ r- 0\}^{\infty}_{r=4}\), \(\{H_ r-(r,0)\}^{\infty}_{r=4}\). In both cases \(H_ r\) denotes a graph with vertex set \(I=\{0,1,2,...,2r\}\) the arcs of which are ordered pairs (i,j), i,j\(\in I\), where \(j=i+1\), \(i+2,...,i+r-1\), \(i+r+1 (mod 2r)\). For \(m>2\) the authors construct the uniquely colourable m-dichromatic oriented graphs by induction over m.