Weak coloring


In graph theory, a weak coloring is a special case of a graph labeling. A weak -coloring of a graph assigns a color to each vertex, such that each non-isolated vertex is adjacent to at least one vertex with different color. In notation, for each non-isolated, there is a vertex with and.
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.

Properties

A graph vertex coloring is a weak coloring, but not necessarily vice versa.
Every graph has a weak 2-coloring. The figure on the right illustrates a simple algorithm for constructing a weak 2-coloring in an arbitrary graph. Part shows the original graph. Part shows a breadth-first search tree of the same graph. Part shows how to color the tree: starting from the root, the layers of the tree are colored alternatingly with colors 1 and 2.
If there is no isolated vertex in the graph, then a weak 2-coloring determines a domatic partition: the set of the nodes with is a dominating set, and the set of the nodes with is another dominating set.

Applications

Historically, weak coloring served as the first non-trivial example of a graph problem that can be solved with a local algorithm. More precisely, if the degree of each node is odd and bounded by a constant, then there is a constant-time distributed algorithm for weak 2-coloring.
This is different from vertex coloring: there is no constant-time distributed algorithm for vertex coloring; the best possible algorithms require communication rounds. Here is the iterated logarithm of .