Abstract:
This article is a continuation of the work started in [1], where $L(2,1)$-coloring problem is interpreted as optimization task on the set of graph vertices. This approach enabled us to reduce solution of hamiltonian cycle problem to injective $\lambda$-coloring. Here we calculate edge distance from the given graph to the nearest graph containing hamiltonian path, also we construct hamiltonian graphs with at most one extra edge.