Complexity of subgraph colorability problems

We introduce a subgraph colorability problem (SCP) and study the complexity. SCP is a generalized node colorability problem related to Ramsey number. From the fact that node 2-colorability problem is in P and k-colorability problem (k ≥ 3) is NP-complete, the increase in the chromatic number makes the problem hard. We study how complexity varies by given graphs when the chromatic number is fixed by using SCP. We show that for k ≥ 2, SCP(K1,k, K2) is NP-complete, and for m, n ≥ 1, SCP(Hm, Hn) is in P, where we let Hl be a graph which has l edges and whose edges are not adjacent to each other.