Coloring, Clique and Independent set

Chromatic number

The graph coloring problem for an undirected graph G, is to assign a color to each summit so that the same color is not assigned to two adjacent vertices.

When the graph is planar, it comes down to the problem of coloring a map.

The minimum number of colors needed to color the graph G is called the chromatic number of G, and is denoted X(G).

The problem of finding the chromatic number of a graph is an Np-complete problem. The problem of coloring a graph with a limited number of colors – is it possible to color the graph with x colors, if so how? – is also an Np-complete problem.

Some rules (without demonstration):

  1. A planar graph is at most 4-chromatic.
  2. A path is 2-chromatic.
  3. A cycle is at most 3-chromatic.
  4. A n-clique (complete graph) is n-chromatic.

Clique – Complete graph

Given an undirected graph G, a clique is a subset of vertices that are all connected in pairs by edges. In other words, it is a complete sub-graph.

Finding a click k of order k in a graph is an Np-complete problem.

The following graph has a clique of order 5:

grapheclique

Independent set

Given an undirected graph G, an independent set is a subset of vertices that are not connected in pairs by edges. Find an independent set is the same to find a clique in the inverse graph, ie it has an edge if it does not exist in the original graph, and vice versa.

To find an independent set a of order k in a graph is a Np-complete problem.

280px-independent_set_graph-svg

Relationship between the three problems and heuristics

An independent set S of G is said to be maximal by inclusion if there is no independent set S’ of G such that S is strictly contained in S’. A clique K is maximal by inclusion if there are no cliques K’ of G such that K is strictly contained in K’.

By this definition, we deduce that an independent set of maximum order is also a maximum stable by inclusion, the reciprocal is not true. We deduce the following heuristic (in french):

stable2

The Brélaz algorithm is a greedy algorithm that allows to know a maximum bound of the chromatic number of a graph. Its principle is simple and proceeds iteratively.

As long as there is an unicoloured vertex, we choose the unstained vertex with the largest number of neighbors colored with different colors. This vertex is then colored with the smallest possible color (the colors are sorted in an arbitrary increasing order). If all existing colors are already used by a neighbor, we add a new color to our palette (adding a color with a value greater than all existing ones).

The notion of independent set can also provide indications on the coloring of a graph. Indeed, we can assume that in an independent set, all the vertices have the same color. The coloration in k colors amounts to finding a partition of the set of vertices in a k independent set.

Welsh & Powell algorithm is based on this proposition:

  1. Classify the vertices of the graph in descending order of their degree
  2. Looking through the list in order, assign a color not used in the first non-colored vertex p, and assign that color to each non-colored vertices which are not adjacent to the summit p.
  3. Return to 2 if there are non-colored vertices in the list. Otherwise return the list.

 

Publicités