摘 要: | For two positive integers k and d such that k ≥ 2d, Gkd is the graph with vertex set {0,1, ...,k-1} in which ij is an edge if and only if d ≤ |i-j| ≤ k-d. Clearly, Gk1 is a complete graph of k vertices and we always assume d ≥ 2 in the following. It is easy to see (also 1]) that a graph G is (k, d)-colorable if and only if there exists a homomorphism from G to Gkd.
|