When the graph is planar, it comes down to the problem of coloring a map. The problem of coloring a graph arises in many practical areas such as pattern matching, sports scheduling, designing seating plans, exam timetabling, the scheduling of taxis, and solving Sudoku puzzles.
Example: A given set of jobs need to be assigned to time slots, each job requires one such slot. Jobs can be scheduled in any order, but pairs of jobs may be in conflict in the sense that they may not be assigned to the same time slot, for example because they both rely on a shared resource. The corresponding graph contains a vertex for every job and an edge for every conflicting pair of jobs. The chromatic number of the graph is exactly the minimum makespan, the optimal time to finish all jobs without conflicts.
Clique – Complete graph
The following graph has a clique of order 5:
Relationship between the three problems and heuristics
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):
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.
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:
To see the connection between Sudoku and graph coloring, we will first describe the Sudoku graph, which for convenience we will refer to as S. The graph S has 81 vertices, with each vertex representing a cell. When two cells cannot have the same number (either because they are in the same row, in the same column, or in the same box) we put an edge connecting the corresponding vertices of the Sudoku graph S. For example, since cells a3 and a7 are in the same row, there is an edge joining their corresponding vertices; there is also an edge connecting a1 and b3 (they are in the same box), and so on. When everything is said and done, each vertex of the Sudoku graph has degree 20, and the graph has a total of 810 edges. S is too large to draw, but we can get a sense of the structure of S by looking at a partial drawing. The drawing shows all 81 vertices of S, but only two (a1 and e5) have their full set of incident edges showing.
The second step in converting a Sudoku puzzle into a graph coloring problem is to assign colors to the numbers 1 through 9. This assignment is arbitrary, and is not a priority ordering of the colors as in the greedy algorithm, it’s just a simple correspondence between numbers and colors.
Once we have the Sudoku graph and an assignment of colors to the numbers 1 through 9, any Sudoku puzzle can be described by a Sudoku graph where some of the vertices are already colored (the ones corresponding to the givens). To solve the Sudoku puzzle all we have to do is color the rest of the vertices using the nine colors.