Subject | Algorithm Design |
---|

A **proper coloring** of a graph is an assignment of colors to the vertices of the graph so that no two adjacent vertices have the same color.

Usually we drop the word "proper'' unless other types of coloring are also under discussion. Of course, the "colors'' don't have to be actual colors; they can be any distinct labels—integers, for example. If a graph is not connected, each connected component can be colored independently; except where otherwise noted, we assume graphs are connected. We also assume graphs are simple in this section.

Graph coloring has many applications in addition to its intrinsic interest.

Actual colors have nothing at all to do with this, graph coloring is used to solve problems where you have a limited amount of resources or other restrictions. The colors are just an abstraction for whatever resource you're trying to optimize, and the graph is an abstraction of your problem.

There are plenty of resources about graph theory on the web, so in a nutshell - a graph is an abstract representation of a set of elements (called vertices), some of which share a connection (called an edge). This of course is the most basic concept, there are many other attributes that can be added on top of that, such as directed edges, weights, and so on, but this concept should be enough for now.

Graphs are often used to model various real-world problems (and sometimes also made-up problems, because mathematicians and computer scientists still have to keep publishing papers after all), and we now have many algorithms that work on them efficiently (in terms of complexity), finding various attributed that may be interesting in order to solve the aforesaid problems.