Graph theory has uncovered many secrets of networks and relationships, but some problems remain unsolved. Here are three famous unsolved problems in graph theory, the Total Coloring Conjecture, the Hadwiger Conjecture, and the 1-Factorization Conjecture, and why they continue to puzzle mathematicians.
Building Blocks of Graph Theory
In mathematics, a graph consists of points known as vertices and any connections between those points called edges. Any two vertices in a graph either are or aren’t connected by an edge between them. This type of graph is not to be confused with the graph of a function, which is a different thing entirely. The study of graphs is called graph theory.
One special type of graph is a regular graph, where each vertex has the same number of neighbors (vertices connected to it by an edge). A vertex’s number of neighbors is called its degree. A graph where every vertex has degree k is called a k-regular graph. For instance, a polygon-shaped graph would be a 2-regular graph since each vertex has two neighbors.
The set of a graph’s vertices is called its vertex set, and the set of its edges is called its edge set. You can build a new graph using subsets of these vertex and edge sets. The result is called a subgraph of the original graph. A subgraph is called a spanning subgraph if it contains all the vertices of the original graph because it spans over all of those vertices. However, it does not have to contain all the edges of the original graph.
A spanning subgraph is also called a factor of the original graph, and if it is k-regular, then it is called a k-factor. In particular, a 1-factor is also called a perfect matching, where you can match each vertex with exactly one neighbor. If you can find a collection of k-factors of a graph where each edge of the graph is used in exactly one of these k-factors, then you have a k-factorization of the original graph.
1-Factorization Conjecture
Now for a challenge. Let’s choose a counting number n. If n is odd, choose another counting number k greater than or equal to 2n. Otherwise, choose k to be greater than or equal to n − 1. Then let’s draw a k-regular graph with 2n vertices. For instance, k = 7 and n = 4 gives us a 7-regular 8-vertex graph.
Whatever graph you drew, does it have a 1-factorization? According to the 1-factorization conjecture, which is an educated guess, the answer will always be yes. This conjecture is a long unsolved problem. However, it is known that if you make the degree k of a regular graph big enough, a 1-factorization of the graph must eventually be possible.
A better result was obtained in a 1985 paper by British mathematicians Amanda Chetwynd and Anthony Hilton, showing that if k is greater than or equal to 12n/7, a 1-factorization is possible. This is the best result achieved to date.
Unfriendly Partition Conjecture
Let’s visit the world of infinite graphs. In particular, we will consider graphs with countably infinitely many vertices, meaning that the vertices of the graph can be put in a one-to-one correspondence with the set of natural numbers 0, 1, 2, etc. Note that in set theory we call zero a natural number.
Now let’s consider grouping these vertices into two different sets so that each vertex is contained in exactly one of these sets and neither set is empty. Each new set is a subset of the set of all vertices. If you group all the elements of any set into any number of subsets in this way, the result is called a partition. To distinguish which vertex is in which subset, let’s color them differently, say orange and green.
Let’s consider a green vertex and count how many green neighbors it has. Let’s say it’s three. Now we’ll count how many orange neighbors it has. Suppose it’s three again. This vertex could be called unfriendly since it has a lot of orange neighbors it doesn’t get along with, and it doesn’t have more green neighbors to compensate. Suppose this applies to each vertex that has at least as many other-colored neighbors as it has same-colored neighbors. If this is true of every vertex in the infinite graph, what we have is called an unfriendly partition.
We will now assume the role of a spiteful god with two crayons. We want to color every vertex to form an unfriendly partition. Supposing we are given an arbitrary countably infinite graph, can we always succeed? Mathematicians have guessed that the answer is yes, creating the unfriendly partition conjecture.
A version of the conjecture also existed in the uncountable case, where numbering the vertices with natural numbers is impossible. However, it has been disproven by Israeli mathematician Saharon Shelah and Canadian mathematician Eric Charles Milner, though they also showed that adding a third color does the trick. For now, the two-color countable case remains open, so whether our divine ambitions can be fulfilled remains to be seen.
Hadwiger Conjecture
The Hadwiger conjecture is a conjecture in graph theory, not to be confused with the Hadwiger conjecture in combinatorial geometry. Let’s start with colorings. In map coloring, we like to ensure that no neighboring regions have the same color. Similarly, a proper vertex coloring of a graph, or just coloring for short, assigns each vertex a color so no neighboring vertices are the same color.
The minimum number of colors required to color a graph is called the graph’s chromatic number. Here the word chromatic means relating to color. For example, the chromatic number of a hexagonal graph is two. The chromatic number of a graph G is denoted by χ(G) with the Greek letter chi.
Now let’s take a graph and start destroying the vertices and edges we don’t like. We can also merge two connected vertices into one, eliminating the connecting edge in the process. This is called edge contraction. Doing these things however we like, our resulting graph is called a minor of the original graph.
Our final required concept is called a complete graph. This is simply a graph where every vertex is connected by an edge to every other vertex. A complete graph of n vertices is denoted by Kₙ. For example, if you draw a square and its diagonals, the resulting graph is called K₄.
Now suppose we have some graph called G (not allowing a loop, which is an edge that connects a vertex to itself). Now suppose we can’t make a minor of G which is a complete graph with t vertices for some value of t. In other words, Kₜ cannot be a minor of G. In that case, the Hadwiger conjecture states that the chromatic number of G must be less than t.
As an example, we’ll suppose that t is 7. That means we can’t transform G into a complete graph on seven vertices using vertex deletions, edge deletions, and edge contractions. If the conjecture is true, then G’s chromatic number χ(G) must be six or less, meaning we’ll need six or fewer colors for a proper vertex coloring on G.
The Hadwiger conjecture was proposed by Swiss mathematician Hugo Hadwiger in 1943, and it remains unsolved today. One major paper on the topic was published in 1980 entitled “Hadwiger’s Conjecture is True for Almost Every Graph,” which proves exactly what its title says. The paper was co-authored by American mathematician Paul Catlin, Hungarian-British mathematician Béla Bollobás, and Hungarian mathematician Paul Erdős, the latter of Erdős number fame. The paper’s authors called the conjecture one of the deepest unsolved problems in graph theory.
Total Coloring Conjecture
We’ve already looked at coloring the vertices of a graph, but we can color the edges as well. Let’s take a graph and color all of the vertices and edges. We can’t color adjacent edges or vertices the same, and we also can’t color an edge the same as one of its endpoints. Once we are done, what we have is called a total coloring of the graph. If we do it in as few colors as possible, then the number of colors we use is the total chromatic number. For a graph G, the total chromatic number is denoted by χ′(G).
Now let’s consider the degrees of the vertices of G. As a reminder, a vertex’s degree is the number of neighboring vertices it has. The highest degree a vertex of G has is called the maximum degree of G, denoted by Δ(G).
Given a graph’s maximum degree, what do we know about its total chromatic number? Suppose this maximum degree is seven. That means there must be a vertex of the graph with seven neighbors, so there are seven edges connecting it to those neighbors. All of those edges share a vertex, so they are adjacent to each other, meaning they must all be colored differently. Additionally, the vertex itself must have a different color from those edges, so the total number of required colors for this graph can’t be any less than eight.
In general, the total chromatic number of a graph is always greater than or equal to its maximum degree plus one. Now that we have a lower bound on the graph’s total chromatic number in terms of its maximum degree, can we find an upper bound? Well, we do have a guess for one, that being the total coloring conjecture by Iranian mathematician Mehdi Behzad and Ukrainian mathematician Vadim Vizing. It states that the total chromatic number of a graph is at most its maximum degree plus two.
This would very tightly constrain a graph’s total chromatic number to be either one more or two more than its maximum degree. Note that we do now have a proven upper bound of the form Δ(G) plus a constant. It’s just that the constant is 10²⁶, not two. As you can see, there is probably some room for improvement.
Leave a Reply