Weak coloring

In

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) \neq 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.

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 (a) shows the original graph. Part (b) shows a breadth-first search tree of the same graph. Part (c) shows how to color the tree: starting from the root, the layers of the tree are colored alternatingly with colors 1 (dark) and 2 (light).

If there is no

domatic partition: the set of the nodes with

c (v) = 1

is a dominating set

, and the set of the nodes with

c (v) = 2

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 (a distributed algorithm that runs in a constant number of synchronous communication rounds). 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.^[1]

This is different from (non-weak)

vertex coloring: there is no constant-time distributed algorithm for vertex coloring; the best possible algorithms (for finding a minimal but not necessarily minimum coloring) require