Graph Coloring You Can See

Introduction

is the computational activity of assigning colours to components of a graph in order that adjoining components by no means share the identical colour. It has functions in a number of domains, together with sports activities scheduling, cartography, avenue map navigation, and timetabling. Additionally it is of great theoretical curiosity and a typical topic in university-level programs on graph idea, algorithms, and combinatorics.

A graph is a mathematical construction comprising a set of nodes through which some pairs of nodes are linked by edges. Given any graph,

• A node coloring is an task of colours to nodes so that every one pairs of nodes joined by edges have completely different colours,
• An edge coloring is an task of colours to edges so that every one edges that meet at a node have completely different colours,
• A face coloring of a graph is an task of colours to the faces of considered one of its planar embeddings (if such an embedding exists) in order that faces with widespread boundaries have completely different colours.

Examples of those ideas are proven within the pictures above. Observe within the final instance that face colorings require nodes to be organized on the airplane in order that not one of the graph’s edges intersect. Consequently, they’re solely potential for planar graphs. In distinction, node and edge colorings are potential for all graphs. The goal is to search out colorings that use the minimal (optimum) variety of colours, which is an NP-hard drawback typically.

Articles on this discussion board (right here, right here and right here) have beforehand thought-about graph coloring, focusing totally on constructive heuristics for the node coloring drawback. On this article we contemplate node, edge, and face colorings and search to deliver the subject to life by means of detailed, visually participating examples. To do that, we make use of the newly created GCol, library an open-source Python library constructed on high of NetworkX. This library makes use of each exponential-time actual algorithms and polynomial-time heuristics.

The next Python code makes use of GCol to assemble and visualize node, edge, and face colorings of the graph seen above. A full itemizing of the code used to generate the photographs on this article is on the market right here. An prolonged model of this text can be accessible right here.

import networkx as nx
import matplotlib.pyplot as plt
import gcol

G = nx.dodecahedral_graph()

# Generate and show a node coloring
c = gcol.node_coloring(G)
nx.draw_networkx(G, node_color=gcol.get_node_colors(G, c))
plt.present()

# Generate and show an edge coloring
c = gcol.edge_coloring(G)
nx.draw_networkx(G, edge_color=gcol.get_edge_colors(G, c))
plt.present()

# Generate node positions after which 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.present()

Node Coloring

Node coloring is probably the most basic of the graph coloring issues. It is because edge and face coloring issues can at all times be transformed into cases of the node coloring drawback. Particularly:

• An edge coloring of a graph might be achieved by coloring the nodes of its line graph,
• A face coloring of a planar graph might be discovered by coloring the nodes of its twin graph.

Edge and face coloring issues are subsequently particular circumstances of the node coloring drawback, regarding line graphs and planar graphs, respectively.

When visualizing node colorings, the spatial placement of the nodes impacts interpretability. Good node layouts can reveal structural patterns, clusters, and symmetries, whereas poor layouts can obscure them. One choice is to make use of force-directed strategies, which mannequin nodes as mutually repelling components and edges as springs. The tactic then adjusts the node positions to attenuate an power perform, balancing the attracting forces of edges and the repulsive forces from nodes. The goal is to create an aesthetically pleasing format the place teams of associated nodes are shut, unrelated nodes are separated, and few edges intersect.

The colorings within the pictures above reveal the consequences of various node positioning schemes. The primary instance makes use of randomly chosen positions, which appears to provide a somewhat cluttered diagram. The second instance makes use of a force-directed methodology (particularly, NetworkX’s spring_layout() routine), leading to a extra logical format through which communities and construction are extra obvious. GCol additionally permits nodes to be positioned primarily based on their colours. The third picture positions the nodes on the circumference of a circle, placing nodes of the identical colour in adjoining positions; the second arranges the nodes of every colour into columns. In these circumstances, the construction of the answer is extra obvious, and it’s simpler to look at that nodes of the identical colour can’t have edges between them.

Node colorings are often simpler to show when the variety of edges and colours is small. Typically, the nodes even have a pure positioning that aids interpretation. Examples of such graphs are proven within the following pictures. The primary three present examples of bipartite graphs (graphs that solely want two colours); the rest present graphs that require three colours.

Edge Coloring

Edge colorings require all edges ending at a specific node to have a distinct colour. Because of this, for any graph $G$ the minimal variety of colours wanted is at all times larger than or equal to $Delta(G)$, the place $Delta(G)$denotes the utmost diploma in $G$. For bipartite graphs, Konig’s theorem tells us that $Delta(G)$ colours are at all times adequate.
Vizing’s theorem offers a extra basic outcome, stating that, for any graph $G$, not more than $Delta(G)+1$ colours are ever wanted.

Edge coloring has functions within the building of sports activities leagues, the place a set of groups are required to play one another over a collection of rounds. The primary instance above reveals an entire graph on six nodes, one node per workforce. Right here, edges symbolize matches between groups, and every colour offers a single spherical within the schedule. Therefore, the “darkish blue” spherical includes matches between Groups 0 and 1, 2 and three, and 4 and 5, for instance. The opposite pictures above present optimum edge colorings of two of the graphs seen earlier. These examples are paying homage to crochet doily patterns or, maybe, Ojibwe dream catchers.

Edge colorings of two additional graphs are proven under. These assist as an instance how, utilizing edge coloring, walks round a graph might be specified by a beginning node and a sequence of colours that specify the order through which edges are then adopted. This offers an alternate approach of specifying routes between areas in avenue maps.

Face Coloring

The well-known four-color theorem states that face colorings of planar embeddings by no means require greater than 4 colours. This phenomenon was first famous in 1852 by Francis Guthrie whereas coloring a map of the counties of England; nevertheless, it might take over 100 years of analysis for it to be formally proved.

The above pictures present face colorings of three graphs. Right here, nodes needs to be assumed wherever edges are seen to satisfy. On this determine, the central face of the Thomassen graph illustrates why 4 colours are typically wanted. As proven, this central face is adjoining to 5 surrounding faces. Collectively, these 5 faces kind an odd-length cycle, essentially requiring three completely different colours, so the central face should then be allotted to a fourth colour. A fifth colour won’t ever be wanted, although.

Face colorings typically want fewer than 4 colours, although. To reveal this, right here we contemplate a particular kind of graph often called Eulerian graph. That is merely a graph through which the levels of all nodes are even. A planar graph is Eulerian if and provided that its twin graph is bipartite; consequently, the faces of Eulerian planar graphs can at all times be coloured utilizing two colours.

Examples of this are proven above the place, as required, all nodes have a fair diploma. Sensible examples of this theorem might be seen in chess boards, Spirograph patterns, and plenty of types of Islamic and Celtic artwork, all of which characteristic underlying graphs which are each planar and Eulerian. Frequent tiling patterns involving sq., rectangular, or triangular tiles are additionally characterised by such graphs, as seen within the well-known “chequered” tiling type.

Two additional tiling patterns are proven under. The primary makes use of hexagonal tiles, the place the primary physique includes a repeating sample of three colours. The second instance reveals an optimum coloring of a lately found aperiodic tiling sample. Right here, the 4 colors are distributed in a much less common method.

Our ultimate instance comes from an notorious spoof article from a 1975 situation of Scientific American. One of many false claims made on this article was {that a} graph had been found whose faces wanted not less than 5 colours, subsequently disproving the 4 colour theorem. This graph is proven under, together with a 4 coloring.

Conclusions and Additional Sources

The article has reviewed and visualized a number of outcomes from the sphere of graph coloring, making use of the open-source Python library GCol. In the beginning, we famous a number of essential sensible functions of this drawback, demonstrating that it’s helpful. This text has centered on visible facets, demonstrating that additionally it is stunning.

The 4 colour theorem, originated from the statement that, when coloring territories on a geographical map, not more than 4 colours are wanted. Regardless of this, cartographers will not be often curious about limiting themselves to simply 4 colours. Certainly, it’s helpful for maps to additionally fulfill different constraints, resembling making certain that every one our bodies of water (and no land areas) are coloured blue, and that disjoint areas of the identical nation (resembling Alaska and the contiguous United States) obtain the identical colour. Such necessities might be modelled utilizing the precoloring and checklist coloring issues, although they could nicely enhance the required variety of colours past 4. Performance for these issues can be included within the GCol library.

All supply code used to generate the figures might be discovered right here. An prolonged model of this text can be discovered right here. All figures have been generated by the writer.