Weak coloring
From Wikipedia, the free encyclopedia
In graph theory, a weak coloring is a special case of a graph labeling. A weak k-coloring of a graph G = (V, E) assigns a color c(v) ∈ {1, 2, ..., k} to each vertex v ∈ V, such that each non-isolated vertex is adjacent to at least one vertex with different color. In notation, for each non-isolated v ∈ V, there is a vertex u ∈ V with {u, v} ∈ E and c(u) ≠ c(v).
The figure on the right shows a weak 2-coloring of a graph. Each dark vertex (color 1) is adjacent to at least one light vertex (color 2) and vice versa.
