On the algorithmic aspects of strong subcoloring

A partition of the vertex set V(G) of a graph G into $$V(G)=V_1\cup V_2\cup \cdots \cup V_k$$ V ( G ) = V 1 ∪ V 2 ∪ ⋯ ∪ V k is called a k-strong subcoloring if $$d(x,y)\ne 2$$ d ( x , y ) ≠ 2 in G for every $$x,y\in V_i$$ x , y ∈ V i , $$1\le i \le k$$ 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 $$\chi _{sc}(G)=\text {min}\{ k:G \text { admits a }k$$ χ sc ( G ) = min { k : G admits a k - $$\text {strong subcoloring}\}$$ 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}$$ K 1 , r -free split graphs, StrongSubcoloring is in P when $$r\le 3$$ r ≤ 3 and NP-complete when $$r>3$$ 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$$ 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,y\in S$$ x , y ∈ S , $$d(x,y)= 2$$ d ( x , y ) = 2 in G and the cardinality of a maximum strong set in G is denoted by $$\alpha _{s}(G)$$ α s ( G ) . Clearly, $$\alpha _{s}(G)\le \chi _{sc}(G)$$ α 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) $$K_{1,4}$$ K 1 , 4 -free split graphs, and it is polynomial time solvable for (i) trees and (ii) $$P_4$$ P 4 -free graphs.