On the algorithmic aspects of strong subcoloring

A partition of the vertex set V(G) of a graph G into (V(G)=V_1cup V_2cup cdots cup V_k) is called a k-strong subcoloring if (d(x,y)ne 2) in G for every (x,yin V_i), (1le i le k) where d(x, y) denotes the length of a shortest x-y path in G. The strong subchromatic number is defined as (chi _{sc}(G)=text {min}{ k:G text { admits a }k)-(text {strong subcoloring}}). In this paper, we explore the complexity status of the StrongSubcoloring problem: for a given graph G and a positive integer k, StrongSubcoloring is to decide whether G admits a k-strong subcoloring. We prove that StrongSubcoloring is NP-complete for subcubic bipartite graphs and the problem is polynomial time solvable for trees. In addition, we prove the following dichotomy results: (i) for the class of (K_{1,r})-free split graphs, StrongSubcoloring is in P when (rle 3) and NP-complete when (r>3) and (ii) for the class of H-free graphs, StrongSubcoloring is polynomial time solvable only if H is an induced subgraph of (P_4); otherwise the problem is NP-complete. Next, we consider a lower bound on the strong subchromatic number. A strong set is a set S of vertices of a graph G such that for every (x,yin S), (d(x,y)= 2) in G and the cardinality of a maximum strong set in G is denoted by (alpha _{s}(G)). Clearly, (alpha _{s}(G)le chi _{sc}(G)). We consider the complexity status of the StrongSet problem: given a graph G and a positive integer k, StrongSet asks whether G contains a strong set of cardinality k. We prove that StrongSet is NP-complete for (i) bipartite graphs and (ii) (K_{1,4})-free split graphs, and it is polynomial time solvable for (i) trees and (ii) (P_4)-free graphs.