A proper k-coloring C1, C2, ..., Ck of a graph G is called strong if
for every vertex u in V(G) there exists an index i in {1, 2, ...,
k} such that u is adjacent to every vertex of Ci . We consider classes SCOLOR(k) of strongly k-colorable
graphs and show that the recognition problem of SCOLOR(k) is NP-complete for every
k >= 4, but it is polynomial-time solvable for k = 3. We give a
characterization of SCOLOR(3)
in terms of forbidden induced subgraphs. Finally, we solve the problem
of uniqueness of a strong 3-coloring.
DIMACS Home Page