## 2 Related Works, Definitions, and Preliminaries
### Optimal Strict Colourings of Mixed Graphs and Equivalent Unit-Time Job-Shop Problems
**_The dedicated processors \(M=\left\{M_{1},M_{2},M_{3},M_{4}\right\}\) must process jobs \(J=\left\{I_{1},J_{2},J_{3},J_{4},J_{5}\right\}\), where processing the job \(J_{1}\in J\) consists of the singleton \(V^{(1)}=\left\{v_{1}\right\}\). The job \(J_{2}\in J\) is represented as a union of the path \((v_{2},v_{3})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{2},v_{3})\) in the graph \((V,\varnothing,E)\). The job \(J_{3}\in J\) contains the set \(V^{(3)}=\left\{v_{4},v_{5},v_{6},v_{7}\right\}\) of the ordered operations \((v_{4},v_{5},v_{6},v_{7})\). The job \(J_{3}\in J\) is represented as a union of the path \((v_{4},v_{5},v_{6},v_{7})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{4},v_{5},v_{6},v_{7})\) in the graph \((V,\varnothing,E)\). The job \(J_{4}\in J\) contains the set \(V^{(4)}=\left\{v_{8},v_{9},v_{10}\right\}\) of the linearly ordered operations \((v_{8},v_{9},v_{10})\). The job \(J_{4}\in J\) is represented as a union of the path \((v_{8},v_{9},v_{10})\) in the directed graph \((V,A,\varnothing)\) and the \((v_{8},v_{9},v_{10})\) in graph \((V,\varnothing,E)\). The job \(J_{5}\in J\) contains the set \(V^{(5)}=\left\{v_{11},v_{12}\right\}\) of the ordered operations \((v_{11},v_{12})\). The job \(J_{5}\in J\) is represented as a union of the path \((v_{11},v_{12})\) in directed graph \((V,A,\varnothing)\) and the chain \((v_{11},v_{12})\) in graph \((V,\varnothing,E)\)._  
Let the set \(V_{1}=\left\{v_{1},v_{5},v_{7}\right\}\) be defined as a set of operations processed on the processor \(M_{1}\). The forbidance to process the operations of the set \(V_{1}\) simultaneously is determined by the clique \(\left\{v_{1},v_{5},v_{7}\right\}\) in the graph \((V,\varnothing,E)\); see Figure 1. Let the processor \(M_{2}\) have to process the operations \(V_{2}=\left\{v_{2},v_{4}\right\}\). The forbidance to process operations of the set \(V_{2}\) simultaneously is determined by the edge \(\left[v_{2},v_{4}\right]\). Let the processor \(M_{3}\) have to process the operations \(V_{3}=\left\{v_{3},v_{9},v_{11}\right\}\). The forbiddance to process operations of the set \(V_{3}\) simultaneously is determined by the clique \(\left\{v_{3},v_{9},v_{11}\right\}\). Let the processor \(M_{4}\) have to process the operations \(V_{3}=\left\{v_{9},v_{11},v_{15}\right\}\). The forbidance to process any pair of operations of the set \(V_{3}\) simultaneously is determined by the clique \(\left\{v_{9},v_{11},v_{15}\right\}\). Let the processor \(M_{4}\) have to process the operations \(V_{4}=\left\{v_{6},v_{8},v_{10},v_{12}\right\}\). The forbidance to process any pair of operations of the set \(V_{4}\) simultaneously is determined by the clique \(\left\{v_{6},v_{8},v_{10},v_{12}\right\}\). A specific colour is used for indicating the operations \(V_{i}=\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|V_{i}|}}\right\}\subseteq V\) that are processed on the processor \(M_{i}\in M_{i}\); see Figure 1. It is clear that the mixed graph depicted in Figure 1 possesses properties (1), (a) and (b), and the indexing of all vertices of the set \(V\) satisfies Remark 1. The optimal colouring of the mixed graph \(G\) is defined as follows: \(\text{c}(\text{v}_{1})=1\), \(\text{c}(\text{v}_{2})=2\), \(\text{c}(\text{v}_{3})=3\), \(\text{c}(\text{v}_{4})=1\), \(\text{c}(\text{v}_{5})=2\), \(\text{c}(\text{v}_{6})=3\), \(\text{c}(\text{v}_{7})=4\), \(\text{c}(\text{v}_{8})=1\), \(\text{c}(\text{v}_{9})=2\), \(\text{c}(\text{v}_{10})=4\), \(\text{c}(\text{v}_{11})=1\) and \(\text{c}(\text{v}_{12})=2\). The optimality of the colouring \(\text{c}(\text{G})\) follows from the fact that the graph \((V,\varnothing,E)\) contains the chain  
Figure 1: Mixed graph \(G\) that determines input data for Example 1. \((v_{4},v_{5},v_{6},v_{7})\) with four vertices and the digraph \((V,A,\varnothing)\) contains the path \((v_{4},v_{5},v_{6},v_{7})\). So, the chromatic number \(\chi(G)\) is not less than four. The optimality of the colouring \(\mathrm{c}(\mathrm{G})\) follows also from the clique \(\{v_{6},v_{8},v_{10},v_{12}\}\).