1 Answers
In graph theory, a weak coloring is a special case of a graph labeling. A weak k-coloring of a graph G = assigns a color c ∈ {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 ≠ c.
The figure on the right shows a weak 2-coloring of a graph. Each dark vertex is adjacent to at least one light vertex and vice versa.
5 views
Answered