2003-24: A new kind of graph colorings

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