Set colorings in perfect graphs
Ralucca Gera, Futaba Okamoto, Craig Rasmussen, Ping Zhang (2011)
Mathematica Bohemica
Similarity:
For a nontrivial connected graph , let be a vertex coloring of where adjacent vertices may be colored the same. For a vertex , the neighborhood color set is the set of colors of the neighbors of . The coloring is called a set coloring if for every pair of adjacent vertices of . The minimum number of colors required of such a coloring is called the set chromatic number . We show that the decision variant of determining is NP-complete in the general case, and show that...