Weak coloring

Summary

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) \in \{1, 2, ..., k$} to each vertex $v \in V$, such that each non-isolated vertex is adjacent to at least one vertex with different color. In notation, for each non-isolated $v \in V$, there is a vertex $u \in V$ with $\{u, v\} \in E$ and $c(u) \ne c(v)$.