{{Short description|Special case of graph labeling in graph theory}} thumb|100px|Weak 2-coloring. In graph theory, a '''weak coloring''' is a special case of a graph labeling. A weak {{mvar|k}}-coloring of a graph {{math|1=''G'' = (''V'', ''E'')}} assigns a color {{math|''c''(''v'') ∈ {1, 2, ..., ''k''}}} to each vertex {{math|''v'' ∈ ''V''}}, such that each non-isolated vertex is adjacent to at least one vertex with different color. In notation, for each non-isolated {{math|''v'' ∈ ''V''}}, there is a vertex {{math|''u'' ∈ ''V''}} with {{math|{''u'', ''v''} ∈ ''E''}} and {{math|''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. thumb|150px|Constructing a weak 2-coloring.
==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 isolated vertex in the graph {{mvar|G}}, then a weak 2-coloring determines a domatic partition: the set of the nodes with {{math|1=''c''(''v'') = 1}} is a dominating set, and the set of the nodes with {{math|1=''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.<ref name="naor-stockmeyer-1995">{{citation | last1 = Naor | first1 = Moni | author1-link = Moni Naor | last2 = Stockmeyer | first2 = Larry | author2-link = Larry Stockmeyer | doi = 10.1137/S0097539793254571 | mr = 1361156 | issue = 6 | journal = SIAM Journal on Computing | pages = 1259–1277 | title = What can be computed locally? | volume = 24 | year = 1995| citeseerx = 10.1.1.29.669 }}.</ref>
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 {{math|''O''({{log-star}} {{pipe}}''V''{{pipe}})}} communication rounds.<ref name="naor-stockmeyer-1995"/><ref>{{citation | last = Linial | first = Nathan | authorlink = Nati Linial | doi = 10.1137/0221015 | mr = 1148825 | issue = 1 | journal = SIAM Journal on Computing | pages = 193–201 | title = Locality in distributed graph algorithms | volume = 21 | year = 1992| citeseerx = 10.1.1.471.6378}}.</ref><ref>{{citation | last1 = Cole | first1 = Richard | last2 = Vishkin | first2 = Uzi | author2-link = Uzi Vishkin | doi = 10.1016/S0019-9958(86)80023-7 | mr = 853994 | issue = 1 | journal = Information and Control | pages = 32–53 | title = Deterministic coin tossing with applications to optimal parallel list ranking | volume = 70 | year = 1986| doi-access = free }}.</ref> Here {{math|{{log-star}} ''x''}} is the iterated logarithm of {{mvar|x}}.
==References== {{reflist}}
Category:Graph coloring Category:Distributed algorithms Category:Distributed computing problems