graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a weak coloring is a special case of a

graph labeling In the mathematical discipline of graph theory, a graph labelling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph. Formally, given a graph , a vertex labelling is a function of to a set o ...

. A weak -coloring of a graph assigns a color to each vertex , such that each non-

isolated vertex In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of ve ...

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 (color 1) is adjacent to at least one light vertex (color 2) and vice versa.

Properties

A graph

vertex coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

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 Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...

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

in the graph , then a weak 2-coloring determines a

domatic partition In graph theory, a domatic partition of a graph G = (V,E) is a partition of V into disjoint sets V_1, V_2,...,V_K such that each ''Vi'' is a dominating set for ''G''. The figure on the right shows a domatic partition of a graph; here the dominating ...

: the set of the nodes with is a

dominating set In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for . The 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 (a

distributed algorithm A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific ...

that runs in a constant number of synchronous communication rounds). More precisely, if the

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...

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 (non-weak)

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

iterated logarithm In computer science, the iterated logarithm of n, written n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. The simplest formal definition i ...

of .

References

{{reflist Graph coloring Distributed algorithms Distributed computing problems