A new kind of graph coloring |
| |
Authors: | Igor E. Zverovich |
| |
Affiliation: | RUTCOR – Rutgers Center for Operations Research, Rutgers, The State University of New Jersey, 640 Bartholomew Road, Piscataway, NJ 08854-8003, USA |
| |
Abstract: | A proper k-coloring C1,C2,…,Ck of a graph G is called strong if, for every vertex uV(G), there exists an index i{1,2,…,k} such that u is adjacent to every vertex of Ci. We consider classes of strongly k-colorable graphs and show that the recognition problem of is NP-complete for every k4, but it is polynomial-time solvable for k=3. We give a characterization of in terms of forbidden induced subgraphs. Finally, we solve the problem of uniqueness of a strong 3-coloring. |
| |
Keywords: | Graph coloring Forbidden induced subgraphs NP-complete problem |
本文献已被 ScienceDirect 等数据库收录! |
|