Injective $L(2,1)$-coloring as an optimization problem on the set of permutations of graph vertices: domishold graphs

The class of domishold graphs is a nearest extension of a well-studied class of threshold graphs. A linear algorithm for optimal $L(2,1)$-colouring of threshold graphs is known. In this paper we consider the injective $L(2,1)$ colouring problem. This problem is very close to the original $L(2,1)$-coloring, more over for almost all graphs they coincide. We introduce the new interpretation of the injective $L(2,1)$ colouring problem as an optimization problem on the set of permutations of graph vertices. Based on this interpretation and using the decomposition of domishold graphs we present an optimal algorithm that colours domishold graphs in the $O(n+m)$ time and remains linear in $n$ for threshold graphs.