- Šárka Voráčová
Click on the vertices to color them. To change the color, click again on the same vertex.
Label the graph’s vertices with colors such that no two vertices sharing the same edge have the same color. The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted ch. Determine the chromatic number of each connected graph.
Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still a very active field of research.