Coloring graph

A variety of tasks arising from production planning, scheduling inspection, storage and transportation of goods, etc., can often be presented as problems of graph theory, closely related to the so-called “coloring task” . The graphs considered in this part are unoriented and do not have loops.

Let G = (V, E) be an arbitrary graph and {c i , ..., c t } be some set whose elements will be called colors. The t-coloring of a graph G is a map φ of V {{c i , ..., c t } such that for any two distinct adjacent vertices and and v of the graph G, Φ (u)! = Φ (v).
We note that it is not assumed here that φ maps V to the entire set of colors {c i , ..., c t }. We say that the color of Φ (v) is assigned to the vertex v of GV or the vertex of v has the color of Φ (v). We see that the t-coloring of the graph G attributes to each of its vertices one of the t given colors in such a way that any two different adjacent vertices have a different color.

Tricolor coloring Count Petersen

A graph is called t-colored if it possesses t-coloring. A graph is called t-chromatic if it is t-colorable, but not (t - 1) -colorable; the number t in this case is called the chromatic number of the graph G and denoted by x (G).

notice, that
1) 1-chromatics graphs are zero graphs and only they;
2) 2-chromatic graphs are non-zero bipartite graphs and only they;
3) x (K n ) = n and x (G)> = n if the graph G contains the graph K n for a natural number n as a subgraph.

The problem of finding the chromatic number of an arbitrary graph has been the subject of many studies at the end of the 19th and in the current century. Now on this issue a large number of interesting results are known. In this section, we consider an “approximate” algorithm that allows us to find the value of the chromatic number of an arbitrary graph and the coloring of the vertices corresponding to this value.