Editing Graph coloring (section)

=== Modular Coloring ===

Modular coloring is a type of graph coloring in which the color of each vertex is the sum of the colors of its adjacent vertices.

Let {{math|k &ge; 2}} be a number of colors where <math>\mathbb{Z}_k</math> is the set of integers modulo k consisting of the elements (or colors) {{math|0,1,2, ..., k-2, k-1}}. First, we color each vertex in G using the elements of <math>\mathbb{Z}_k</math>, allowing two adjacent vertices to be assigned the same color. In other words, we want c to be a coloring such that c: V(G) &rarr; <math>\mathbb{Z}_k</math> where adjacent vertices can be assigned the same color.

For each vertex v in G, the color sum of {{math|v, &sigma;(v)}}, is the sum of all of the adjacent vertices to v mod k. The color sum of v is denoted by

:{{math|1= &sigma;(v) = &sum;<sub>u &in; N(v)</sub> c(u)}}

where u is an arbitrary vertex in the neighborhood of v, N(v). We then color each vertex with the new coloring determined by the sum of the adjacent vertices. The graph G has a modular k-coloring if, for every pair of adjacent vertices a,b, &sigma;(a) &ne; &sigma;(b). The modular chromatic number of G, mc(G), is the minimum value of k such that there exists a modular k-coloring of G.<

For example, let there be a vertex v adjacent to vertices with the assigned colors 0, 1, 1, and 3 mod 4 (k=4). The color sum would be &sigma;(v) = 0 + 1 + 1+ 3 mod 4 = 5 mod 4 = 1. This would be the new color of vertex v. We would repeat this process for every vertex in G. If two adjacent vertices have equal color sums, G does not have a modulo 4 coloring. If none of the adjacent vertices have equal color sums, G has a modulo 4 coloring.