We study H(p, q)-colorings of graphs, for H a fixed simple graph and p, q natural numbers, a generalization of various other vertex partitioning concepts such as H-covering. An H-cover of a graph G is a local isomorphism between G and H, and the complexity of deciding if an input graph G has an H-cover is still open for many graphs H. In this paper we show that the complexity of H(2p, q)-COLORING is directly related to these open graph covering problems, and answer some of them by resolving the complexity of H(p, q)-COLORING for all acyclic graphs H and all values of p and q.
展开▼
