No-hole \((r+1)\)-distant colorings (Q688267)

Colorings of graphs with consecutive integers such that adjacent vertices get colors that differ by more than a fixed positive integer \(r \geq 1\) are considered. Such colorings are called \(N_ r\)-colorings. Conditions are given that imply a graph has (or does not have) an \(N_ r\)-coloring. For example, it is shown that a graph \(G\) has an \(N_ r\)-coloring if and only if \(\overline G\) has a hamiltonian \(r\)-path (the \(r\)-th power of a path). Several special classes of graphs are considered; for example, it is shown that if \(G\), a graph of order \(n\), has a complete \(k\)-partite subgraph of order \(m\) with \(n-m<(k-1)r\), then \(G\) does not have an \(N_ r\)-colouring. Variations of \(N_ r\)-colorings are considered.