On deeply critical oriented graphs (Q1850516)

The oriented chromatic number \(o(H)\) of an oriented graph (i.e. a digraph without opposite arcs) \(H\) is the minimum order of an oriented graph \(H'\) such that \(H\) has a homomorphism to \(H'\). In other words, \(o(H)\) is the minimum positive integer \(m\) such that there exists a proper (in usual sense) colouring \(f\) of \(V(H)\) with \(m\) colours with the additional property that \[ \forall v,w,u,z\in V(H) ((vw\in E(H) \& uz\in E(H) \& f(v)= f(z))\Rightarrow f(w)\neq f(u)). \] While deleting a vertex or an edge from a graph decreases its chromatic number by at most one, this is not true for the oriented chromatic number. Call an oriented graph \(H\) deeply critical if \(o(H)- o(H- (v,u))= 2\) for every \((v,u)\in E(H)\). The main result of the note is that there are infinitely many deeply critical graphs. For every positive integer \(k\), there exists a deeply critical graph \(G_k\) such that \(o(G_k)- o(G_k- v)\geq k\) for every \(v\in V(G_k)\).