Introduction
is a computational function for assigning colors to elements of a graph so that adjacent elements never have the same color. It has applications in several domains, including sports planning, cartography, road map navigation, and timing. There is also significant theoretical interest and a general course in university-level courses in graph theory, algorithms, and combinatorics.
A graph is a mathematical structure consisting of a set of nodes where other pairs of nodes are connected edges. Given any graph,
- A the color of the nodes is the assignment of colors to the nodes so that all pairs of nodes connected by edges have different colors,
- An edge color is the assignment of colors to the edges so that all the edges that meet in the area have different colors,
- A facial color of a graph assigns colors to the faces of one of its fixed embeddings (if the embedding exists) so that faces with common boundaries have different colors.
Examples of these concepts are shown in the images above. Note in the last example that the face colors require the nodes to be arranged in a plane so that no graph edge intersects. Therefore, they can only occur in ordered graphs. Conversely, node and edge colors can occur in all graphs. The goal is to find colors that use the minimum (maximum) number of colors, which is an NP-hard problem in general.
Articles in this forum (here, here and here) have previously considered graph coloring, focusing mainly on constructive heuristics for the node coloring problem. In this article we consider node, edge, and face colors and want to bring the topic to life with detailed, visual examples. To do this, we use the newly developed GCol, an open source Python library built on top of NetworkX. This library uses both exact-time algorithms and polynomial-time heuristics.
The following Python code uses GCol to construct and visualize the area, edge, and face colors of the graph seen above. A full list of the code used to generate the images in this article is available here. An extended version of this article is available here.
import networkx as nx
import matplotlib.pyplot as plt
import gcol
G = nx.dodecahedral_graph()
# Generate and display a node coloring
c = gcol.node_coloring(G)
nx.draw_networkx(G, node_color=gcol.get_node_colors(G, c))
plt.show()
# Generate and display an edge coloring
c = gcol.edge_coloring(G)
nx.draw_networkx(G, edge_color=gcol.get_edge_colors(G, c))
plt.show()
# Generate node positions and then a face coloring
pos = nx.planar_layout(G)
c = gcol.face_coloring(G, pos)
gcol.draw_face_coloring(c, pos)
nx.draw_networkx(G, pos)
plt.show()Node color
The color of the nodes is the most important in graph coloring problems. This is because edge and face color problems can be converted into node color problems. Specifically:
- The edge coloring of a graph can be achieved by coloring its nodes line graph,
- The face color of a planar graph can be obtained by coloring its nodes dual graph.
Hence, Edge and face color problems special cases of the color node problem, which deals with line graphs and planar graphs, respectively.
When viewing node colors, the spatial placement of nodes affects interpretation. Positive node structures can reveal structural patterns, clusters, and symmetries, while negative structures can hide them. Another option is to use force-directed methods, which model nodes as proportional repellers and edges as springs. The method then adjusts the position of the node to minimize the energy function, balancing the attractive forces at the edges and the repulsive forces from the nodes. The goal is to create a neat structure where groups of related nodes are close together, unrelated nodes are separated, and few edges meet.
The colors in the images above show the results of different node placement schemes. The first example uses randomly selected positions, which seems to give a messy drawing. The second example uses a dynamic approach (specifically, NetworkX's spring_layout() practice), which leads to a rational organization where communities and structure are more visible. GCol also allows nodes to be placed based on their colors. The third image places the nodes in a circular circle, placing nodes of the same color in adjacent areas; the second organizes the nodes of each color into columns. In these cases, the structure of the solution is very visible, and it is easy to see that nodes of the same color cannot have edges between them.
Node colors are usually easier to display when the number of edges and colors is small. Sometimes, nodes also have a natural shape that helps in interpretation. Examples of such graphs are shown in the following images. The first three show examples of double graphs (graphs that only need two colors); the remaining graphs show graphs that require three colors.
Edge Color
Edge colors require that all edges that end at a certain point have a different color. As a result, in any graph the minimum number of colors required is always greater than or equal to it there denotes a greater degree in . For bipartite graphs, Konig's theorem tells us that colors are always enough.
Vizing's theorem gives a general result, say, for any graph no more colors are always needed.
Edge coloring has applications in the construction of sports leagues, where a set of teams are required to play each other over a series of rounds. The first example above shows a complete graph on six nodes, one node per group. Here, the edges represent the similarities between the groups, and each color assigns one cycle to the schedule. Therefore, the “blue” round includes matches between Group 0 and 1, 2 and 3, and 4 and 5, for example. The other images above show the high-quality colors of the two graphs seen earlier. These examples remind us of crochet doily patterns or, perhaps, Ojibwe dream catchers.
The edge colors of two additional graphs are shown below. This helps to show how, using an edge color, a walk around a graph can be specified with a starting point and a sequence of colors specifying the order in which the edges are followed. This provides another way to specify routes between locations on road maps.
Face Color
The famous four color theory states that face colors for embedding in a plane do not need more than four colors. This phenomenon was first noted in 1852 by Francis Guthrie when he colored a map of the counties of England; however, it would take over 100 years of research to be formally proven.
The images above show the face colors of the three graphs. Here, nodes should be considered wherever edges appear to meet. In this illustration, the central face of the Thomassen graph shows why four colors are sometimes needed. As shown, this central face is close to five surrounding faces. Together, these five faces form a cycle of odd length, which requires three different colors, so the middle face must be assigned a fourth color. A fifth color will never be needed, however.
Face colors usually require fewer than four colors, however. To illustrate this, here we consider a special type of graph known as an Eulerian graph. This is simply a graph where the degrees of all nodes are equal. A planar graph is Eulerian if and only if its dual graph is binary; therefore, the faces of Eulerian planar graphs can always be colored using two colors.
Examples of this are shown above where, as required, all nodes have equal degrees. Practical examples of this theory can be seen in chess boards, Spirograph patterns, and many forms of Islamic and Celtic art, all of which include graphs that are both planar and Eulerian. Common tiling patterns of square, rectangular, or triangular tiling are also seen in such graphs, as seen in the well-known “checkered” tiling style.
Two other tiling patterns are shown below. The first one uses hexagonal tiles, where the main body includes a repeating pattern of three colors. The second example shows the correct color of a newly discovered aperiodic tiling pattern. Here, the four colors are distributed in an unusual way.
Our final example comes from an infamous spoof article from a 1975 issue of American science. One of the false claims made in this article was that a graph had been found whose faces required at least five colors, therefore contradicting the four color theory. This graph is shown below, along with four colors.
Conclusions and Other Resources
The article reviewed and visualized several results from the field of graph coloring, using the open source Python library GCol. At the outset, we noted several important ways in which this problem works, which shows that it is useful. This article focuses on the visual aspects, which show that it is good.
The theory of four colors, stems from the observation that, when coloring areas on a geographic map, no more than four colors are needed. Despite this, cartographers often don't want to limit themselves to just four colors. Indeed, it helps that the maps also satisfy other constraints, such as ensuring that all water (and no land areas) are colored blue, and that different areas of the same country (such as Alaska and the contiguous United States) get the same color. Such requirements can be modeled using precoloring and list coloring problems, although they may increase the required number of colors to more than four. The implementation of these problems is also included in the GCol library.
All the source code used to perform the calculations can be found here. An extended version of this article can also be found here. All calculations are done by the author.
