Graph Coloring You Can See

Introduction

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

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

• A node coloring is an project of colours to nodes so that each one pairs of nodes joined by edges have completely different colours,
• An edge coloring is an project of colours to edges so that each one edges that meet at a node have completely different colours,
• A face coloring of a graph is an project of colours to the faces of certainly 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 aircraft 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 purpose is to search out colorings that use the minimal (optimum) variety of colours, which is an NP-hard downside basically.

Articles on this discussion board (right here, right here and right here) have beforehand thought of graph coloring, focusing totally on constructive heuristics for the node coloring downside. On this article we contemplate node, edge, and face colorings and search to convey 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 pictures on this article is obtainable right here. An prolonged model of this text can be obtainable 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 elementary of the graph coloring issues. It is because edge and face coloring issues can all the time be transformed into cases of the node coloring downside. Particularly:

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

Edge and face coloring issues are subsequently particular instances of the node coloring downside, 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 strategy then adjusts the node positions to attenuate an vitality perform, balancing the attracting forces of edges and the repulsive forces from nodes. The purpose 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 display the results of various node positioning schemes. The primary instance makes use of randomly chosen positions, which appears to present a moderately cluttered diagram. The second instance makes use of a force-directed technique (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 based mostly on their colours. The third picture positions the nodes on the circumference of a circle, placing nodes of the identical shade in adjoining positions; the second arranges the nodes of every shade into columns. In these instances, the construction of the answer is extra obvious, and it’s simpler to watch that nodes of the identical shade can’t have edges between them.

Node colorings are normally simpler to show when the variety of edges and colours is small. Generally, 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 selected node to have a special shade. Because of this, for any graph $G$ the minimal variety of colours wanted is all the time higher 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 all the time enough.
Vizing’s theorem offers a extra common end result, stating that, for any graph $G$, not more than $Delta(G)+1$ colours are ever wanted.

Edge coloring has functions within the development of sports activities leagues, the place a set of groups are required to play one another over a sequence of rounds. The primary instance above reveals a whole graph on six nodes, one node per group. Right here, edges signify matches between groups, and every shade offers a single spherical within the schedule. Therefore, the “dark 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 beneath. These assist as an example how, utilizing edge coloring, walks round a graph may be specified by a beginning node and a sequence of colours that specify the order through which edges are then adopted. This gives an alternate method of specifying routes between areas in road 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; nonetheless, 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 type an odd-length cycle, essentially requiring three completely different colours, so the central face should then be allotted to a fourth shade. A fifth shade won’t ever be wanted, although.

Face colorings typically want fewer than 4 colours, although. To display this, right here we contemplate a particular sort of graph often known as 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 all the time 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 may be seen in chess boards, Spirograph patterns, and lots of types of Islamic and Celtic artwork, all of which characteristic underlying graphs which might be each planar and Eulerian. Widespread 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 beneath. The primary makes use of hexagonal tiles, the place the principle physique includes a repeating sample of three colours. The second instance reveals an optimum coloring of a just lately found aperiodic tiling sample. Right here, the 4 colors are distributed in a much less common method.

Our remaining instance comes from an notorious spoof article from a 1975 concern of Scientific American. One of many false claims made on this article was {that a} graph had been found whose faces wanted at the very least 5 colours, subsequently disproving the 4 shade theorem. This graph is proven beneath, together with a 4 coloring.

Conclusions and Additional Assets

The article has reviewed and visualized a number of outcomes from the sector of graph coloring, making use of the open-source Python library GCol. Initially, we famous a number of vital sensible functions of this downside, demonstrating that it’s helpful. This text has centered on visible features, demonstrating that it’s also stunning.

The 4 shade theorem, originated from the commentary that, when coloring territories on a geographical map, not more than 4 colours are wanted. Regardless of this, cartographers usually are not normally taken with limiting themselves to only 4 colours. Certainly, it’s helpful for maps to additionally fulfill different constraints, akin to guaranteeing that each one our bodies of water (and no land areas) are coloured blue, and that disjoint areas of the identical nation (akin to Alaska and the contiguous United States) obtain the identical shade. Such necessities may be modelled utilizing the precoloring and record coloring issues, although they might properly 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 may be discovered right here. An prolonged model of this text may also be discovered right here. All figures have been generated by the creator.