On separating systems of graphs

Given a finite loopless graph G (resp. digraph D), let σ(G), ?(G) and ψ(D) denote the minimal cardinalities of a completely separating system of G, a separating system of G and a separating system of D, respectively. The main results of this paper are:

$\text{δ(G) =}\text{min}\text{m}{}^{\mathrm{m}}{}_{\mathrm{?m/2?}}\text{?γ(G)}\text{and}\text{?(G) = ?}\text{log}{}_2\text{γ(G)?}\text{where}\text{γ(G)}$

denotes the chromatic number of G. (ii) All the problems of determining σ(G), ?(G) and ψ(D) are NP-complete.