graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a weak coloring is a special case of a

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

. 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 Graph (discrete mathematics)#Graph, undirected graph consists of a set of vertices and a s ...

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 methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

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 dept ...

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

, 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 local algorithm is a distributed algorithm that runs in constant time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexi ...

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, scientifi ...

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.. 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 of .

References

{{reflist Graph coloring Distributed algorithms Distributed computing problems