You're viewing this item in the new Europeana website. View this item in the original Europeana.

Set colorings in perfect graphs

For a nontrivial connected graph G, let c : V (G) → N be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v ∈ V (G), the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) 6= NC(v) for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is calle…