Weak coloring

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Weak 2-coloring.

In graph theory, a weak coloring is a special case of a graph labeling. A weak k-coloring of a graph G = (VE) assigns a color c(v) ∈ {1, 2, ..., k} to each vertex vV, such that each non-isolated vertex is adjacent to at least one vertex with different color. In notation, for each non-isolated vV, there is a vertex uU 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.

Constructing a weak 2-coloring.

Properties[edit]

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 isolated vertex in the graph G, then a weak 2-coloring determines a 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[edit]

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 O(log* |V|) communication rounds.[1][2][3] Here log* x is the iterated logarithm of x.

References[edit]

  1. ^ a b Naor, Moni; Stockmeyer, Larry (1995), "What can be computed locally?", SIAM Journal on Computing, 24 (6): 1259–1277, MR 1361156, doi:10.1137/S0097539793254571 .
  2. ^ Linial, Nathan (1992), "Locality in distributed graph algorithms", SIAM Journal on Computing, 21 (1): 193–201, MR 1148825, doi:10.1137/0221015 .
  3. ^ Cole, Richard; Vishkin, Uzi (1986), "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control, 70 (1): 32–53, MR 853994, doi:10.1016/S0019-9958(86)80023-7 .