## DIMACS TR: 2003-24

## A new kind of graph colorings

### Author: Igor Zverovich

**
ABSTRACT
**
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.

AMS Subject Classification: 05C15.

Keywords: Graph coloring, forbidden induced subgraphs, NP-complete
problem.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-24.ps.gz

DIMACS Home Page