For those of you interested in learning some more about the specific mathematical concepts included in my puzzle game Chromagraph, this page explains some of the graphs and graph theory problems included in the game. The intended experience of Chromagraph is for the player to discover the rules for these problems on their own by playing around with the puzzles to see what works and what doesn't. This page is intended for those whom have already completed the game, and will spoil large portions of its contents.
Graph theory is an extremely broad field and includes a large number of completely different topics. Graphs can be used to represent many different phenomena, and depending on what we are using the graph for there are a lot of different questions that we might want to ask about it. As explained on the main project page for this game, graph coloring problems tend to appear whenever the concept of coverage or conflict avoidance is important since their solutions tend to rely on distributing labels over the entire graph in a way that spreads them somewhat evenly.
Each of the eight sections of this game consists of puzzles which explore a real, established sub-field in graph theory. Because I wanted all of the puzzles to use a similar control scheme and visual language, the included problems are all modifications of graph labeling (or problems that can be phrased in the language of graph labeling). The following types of problem are included in the game:
Although there are many different varieties of graph coloring problem, the term "graph coloring" without qualification generally refers to proper vertex coloring. This type of problem is explained on the main project page, and consists of an assignment of colors to each vertex such that adjacent vertices are colored differently. Each puzzle in this section limits the number of colors that can be used to the smallest number for which a proper coloring is possible, which is known as the chromatic number of the graph, \(\chi(G)\). Determining the chromatic number of a general graph is a known hard problem, although there are certain special classes of graph for which specific results are known. A famous example of this is the 1976 four color theorem (which is also famous for being the first computer-assisted proof), which established that any planar graph (a graph that can be drawn in the plane so that none of its edges cross) can be colored with only 4 colors.
Edge coloring is a natural variant of vertex coloring wherein we assign colors to the edges of a graph rather than the vertices, with the restriction that edges sharing an endpoint must be colored differently. The smallest number of required colors is known as the chromatic index of the graph, \(\chi'(G)\). Interestingly, although it is difficult to come up with good general bounds for the number of colors required for vertex coloring, the number of possible colors required for an edge coloring is extremely limited. The obvious lower bound is just the maximum vertex degree (or maximum number of neighbors possessed by any vertex), \(\Delta(G)\), since all edges meeting at a single vertex require different colors, but it's not too hard to see that some graphs require more than that many colors (for example, a triangle graph has maximum degree \(\Delta(G) = 2\) but requires a different color for all three of its edges). However, Vizing's theorem shows that having just one extra color is always enough. This implies that there are only two possible values for the chromatic index of any graph: either \(\chi'(G) = \Delta(G)\) or \(\chi'(G) = \Delta(G)+1\).
After defining vertex coloring and edge coloring the natural continuation is to combine the two, in which case we get total coloring. This consists of a coloring of the vertices and edges of a graph such that (a) the vertex coloring is proper, (b) the edge coloring is proper, and (c) each edge is colored differently from both of its endpoints. The minimum number of colors required to complete a total coloring is the total chromatic number, \(\chi''(G)\). Similar to edge coloring, it is clear that this requires at least \(\Delta(G)+1\) colors (this is the number required to color the vertex of maximum degree plus all incident edges). Good general upper bounds do not exist, but it is conjectured that only one additional color suffices, in which case there would also only be two possible total chromatic numbers: either \(\chi''(G) = \Delta(G)+1\) or \(\chi''(G) = \Delta(G)+2\).
Equitable coloring is one of many variations of the graph coloring problem for which the goal is to find a proper vertex coloring that satisfies an additional set of constraints. In this case the goal is to properly color the graph so that the color classes (the sets of vertices that are all the same color) are as equal as possible in size. For convenience, in Chromagraph all of the equitable coloring puzzles consist of a graph whose vertex count is a multiple of the number of allowed colors, and as a result each color must be used an equal number of times. Equitable coloring is an interesting variant because, unlike standard coloring, it does not necessarily get easier when more colors become available due to the fact that all of the colors must always be used, and there are plenty of examples for which a graph can be colored but not equitably colored with some number of colors (for example, star graphs can always be colored with 2 or more colors, but in general they cannot be equitably colored unless there is a different color available for each vertex).
The dominating set problem represents the first significant departure from graph coloring problems that the game explores (depending on the order in which the player makes it through the levels). A dominating set of a graph is a set of vertices for which every vertex is either in the selected set or adjacent to something in the selected set. The size of the smallest possible dominating set is known as the domination number, \(\gamma(G)\). Within the game this problem is represented in the graph coloring format by allowing the player to color a limited number of vertices to represent the selected set, with the adjacent vertices highlighted to make it easier to tell when everything has been dominated. Unlike all of the above problems, dominating set is about coverage rather than conflict avoidance, and as such it allows adjacent vertices to be selected, causing it to play very differently from the previous sections.
Fall coloring is a somewhat obscure graph coloring problem that I was made aware of by my friend and colleague Chris Mitillos. It is essentially a combination of vertex coloring and dominating set, and the goal is to find a proper coloring such that each color class is, itself, a dominating set. That is, each vertex must be able to "see" every color represented among itself and its neighbors. It is fairly rare for a graph to possess such a coloring, and so most of the work in this area involves coming up with characterizations of families of graph that possess fall colorings. Like equitable coloring, the number of allowed colors also matters quite a lot, and making more colors available generally does not make the problem easier (and may in fact make it impossible).
There are several different varieties of graceful labeling problem, but the common theme is to assign a numerical label to each vertex so that all of the absolute differences in adjacent labels are distinct. In the context of this game the player assigns numerical labels to the vertices, and then the edge labels are automatically calculated as the differences in their endpoints' labels, with the goal of making all vertex and edge labels distinct. The version of this puzzle used in the game is based on the graceful tree conjecture, which holds that all tree graphs (connected graphs without cycles) can be gracefully labeled. In this case we restrict ourselves to consecutive odd integer labels. This is the only puzzle in the game for which the numerical values of the vertex labels are actually significant, with the groups of dots serving only to make the colors more visually distinct in the other puzzle types. While some of the larger arrangements of dots can be difficult to count exactly or visually distinguish at a glance, the fact that the labels for this puzzle are odd numbers means that all labels differ by at least two, which makes it easier to quickly tell which are larger than which and by what approximate margin.
Graph decomposition refers to the process of partitioning the edge set of a graph into multiple copies of a specified subgraph. There are a lot of different types of decomposition problem that can be explored depending on what exactly the graph is being decomposed into. Some examples include cycle decomposition and star decomposition. This section focuses specifically on decomposing a graph into triangles, which has some applications in combinatorial design. The triangle is also a simple and limited enough type of subgraph that it was fairly easy to program the solution verification code.
Most of the graphs that define the various puzzles are actually named, important graphs with well-studied properties. These specific graphs and graph families are explained below. The other puzzles in the game were mostly made by me either randomly generating a graph, slightly modifying an existing graph, or doodling on a piece of paper to try to come up with something that would lead to a challenging puzzle. The images included below were rendered in-game by deactivating all sprites and having the graph elements draw themselves as black geometric objects on a white background. Screenshots were taken of the puzzles in this state in order to isolate the outlines of the graphs for use in creating the main menu puzzle icons. Some of the graphs and graph families included in the game are:
A complete graph on \(n\) vertices, \(K_n\), is a graph for which all possible pairs of vertices are adjacent. Normally these are not very interesting when it comes to graph coloring because, by their nature, all vertices require a different color, but they lead to some interesting results for some of the other puzzle types. For example, \(K_7\) can be decomposed into 7 triangles, which seems to be the go-to illustration that everyone reaches for when they talk about block design (as I saw for about five talks in a row at a combinatorics conference).
A cycle graph on \(n\) vertices, \(C_n\), is a graph that consists entirely of a single closed chain. This is a relatively simple type of graph that often appears as a subgraph in the characterization of other graph properties. For example, a graph is bipartite (i.e. 2-colorable) if and only if it does not contain an odd cycle. Cycles also figure prominently into one of my favorite graph theory problems (and what is by some measures the first ever graph theory result), the Seven Bridges of Königsberg.
A wheel graph on \(n\) vertices, \(W_n\), is constructed by connecting every vertex of a cycle to a single central vertex. Wheel graphs do not show up very often in nature, but they are a relatively simple infinite family of graphs to study, and so are often used in the development of results for restricted sets of graphs.
A tree is any connected graph without cycles. Trees come in an endless variety of shapes and sizes. They arise naturally as a description of certain types of organizational or data structure, but they also often appear as an important subgraph of interest acting as a "skeleton" of sorts for the graph in question, for example in the minimum spanning tree problem and the Steiner tree problem. Importantly for my research, they also appear in the characterization of basic feasible solutions for the minimum-cost network flows problem. Because trees include such a wide variety of graphs, many specified families of tree graph have their own names.
A path graph on \(n\) vertices, \(P_n\), is a simple tree graph consisting of a single chain of vertices in sequence. Finding paths within larger graphs is an extremely important problem in its own right, and forms the basis of navigation software, among many other things. In some sense a path can be thought of as the "least compact" type of tree on \(n\) vertices in that its vertices are as spread out as it is possible to be while still being connected.
A star graph on \(n\) vertices, \(S_n\), is another simple tree graph consisting of a single central vertex adjacent to every other vertex. In some sense a star can be thought of as the "most compact" type of tree on \(n\) vertices in that its vertices are as close together as it is possible to be while avoiding forming any cycles. Although stars and paths are both trees, and are thus both 2-colorable, their difference in degree distribution gives them very different behavior when it comes to most other puzzles.
The Petersen graph, named after Danish mathematician Julius Petersen, is the probably the most famous specific named graph in graph theory. It appears on a lot of textbook covers and in a lot of mathematical art due in part to its large number of very different-looking embeddings. It is important in graph theory because it is a relatively simple graph that acts as a counterexample for a lot of conjectures. For the purposes of this game I decided to go with the classic pentagram embedding because it has 5-fold symmetry, and most of the puzzles for which I used it involved a number of colors other than 5, which prevented the player from simply relying on a symmetric coloring (a design choice which I carried over to many of the other named graphs below).
A polyhedral graph is a graph generated from a polyhedron, with its vertices and edges corresponding to the geometric definitions of those terms. As mentioned on my papercraft page, the dodecahedron graph is largely responsible for the study of Hamiltonian cycles.
A hypercube graph of dimension \(n\), \(Q_n\), is a particular type of polyhedral graph which represents a generalization of the 2-dimensional square or the 3-dimensional cube. As with most high-dimensional polytopes, projecting the shape onto the plane results in a bit of a jumbled mess, but I like that you can still see some of the cubes present in this embedding of \(Q_4\).
The 26-fullerene graph describes the structure of a molecule made from 26 carbon atoms arranged in a somewhat spherical closed mesh. This type of molecule is known as a fullerene, and it comes in many other forms, including larger spheres like buckminsterfullerene and open forms like graphite and carbon nanotubes.
The Grötzsch graph, named after German mathematician Herbert Grötzsch, is one of many graphs defined specifically to have a larger-than-expected chromatic number, which is how I stumbled upon it while looking for puzzle candidates. In particular it is a triangle-free graph that requires 4 colors, which is unexpected since prohibiting triangles tends to make coloring easier by ensuring that vertices cannot be too densely packed. It is one in an infinite series of graphs that is triangle-free but whose chromatic number increases in each generation, proving that triangle-free graphs can have arbitrarily large chromatic numbers.
The Clebsch graph, named after German mathematician Alfred Clebsch (by its discoverer, Dutch mathematician Jaap J. Seidel), was originally used for developing some results in spectral graph theory and Ramsey theory. It also happens to fit into several important infinite families of graphs and to have a lot of nice properties. None of this really mattered to me, however, and I just picked it because it happens to be small enough to be understandable while still being relatively complicated and nontrivial to color.
A grid graph is a graph that represents a regular tiling of the plane. The versions included in the game are based on a limited section of a square tiling. This can be thought of as representing a square game board with a vertex for each tile and edges connecting adjacent tiles. Keeping the board game theme in mind, we can define a king's graph or a knight's graph by using edges to represent the possible moves that those respective chess pieces can make.
In the same way that we can define algebraic operators which combine two numbers to produce another number, there are various graph operators that combine two graphs to produce another graph. One of the simplest of these operators is the Cartesian product, \(G \square H\), which effectively consists of producing a copy of \(G\) for each vertex of \(H\) and defining edges between copied vertices to be analogous to the edges of \(H\). The Cartesian product has a lot of nice algebraic properties, like being commutative and associative, and it is even possible to decompose a graph into "prime" graphs whose Cartesian product is the original graph. It also appears in a lot of graph coloring results because the colorings of the two factors can often be used to come up with a coloring for the product, and in fact a common early exercise for graph theory students is to prove that \(\chi(G \square H) = \max\{\chi(G), \chi(H)\}\). The fall coloring puzzle which includes \(C_5 \square C_5\), in particular, is worth pointing out as an unexpected result because the product is fall colorable in spite of the fact that neither factor is.
Oh, I suppose I should explain what the dart graph is, considering that I used it for the game's logo. It is one of a handful of very small graphs that has been given a cute name based on its shape, like the bowtie graph, the bull graph, and the house graph. As far as I know it does not possess any particularly interesting properties, and I picked it because it looks kind of like the hunter rune from Bloodborne.