A partition of the vertex set V(G) of a graph G into V(G) = V1∪ V2∪ ⋯ ∪ Vk is called a k-strong subcoloring if d(x, y) ≠ 2 in G for every x, y∈ Vi, 1 ≤ i≤ k where d(x, y) denotes the length of a shortest x-y path in G. The strong subchromatic number is defined as χsc(G)=min{k:Gadmits ak-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 K1,r-free split graphs, StrongSubcoloring is in P when r≤ 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 P4; 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, y∈ S, d(x, y) = 2 in G and the cardinality of a maximum strong set in G is denoted by αs(G). Clearly, αs(G) ≤ χ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) K1 , 4-free split graphs, and it is polynomial time solvable for (i) trees and (ii) P4-free graphs. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.