One kind of graph problem that’s extremely widely used in computer science is called graph coloring. There’s two versions of it, *vertex coloring*, and *face coloring*.
Vertex coloring is the one that’s more widely used. Edge coloring problems are all variations on the following: given a graph *G=(V,E)*, find a mapping of colors to vertices, such than if two vertices are adjacent, they’re assigned different colors?
The variants of the vertex coloring problem are things like:
* What’s the *minimum* number of colors (aka the *chromatic number* of the graph)
that can be used to color a graph?
* Given an integer N, can you find an N-coloring of the graph?
The face coloring problem is more complicated to describe. Suppose you have a *planar* graph. (Remember that that means a graph which can be drawn on a plane with no edges crossing.) Suppose further that the graph has the property that from any vertex v, there is a path through the graph from v to v. Then that graph is called a *map*. For a map drawn on a plane, every edge is part of at least one cycle. The smallest possible cycles – that is, the cycles which are not bisected by any other edges of the graph – are called *countries* or *faces* of the graph. The face coloring problem assigns colors to the *faces* of a graph, so that no two faces that share an edge are the same color. There’s an extremely fascinating proof that any planar map can be face-colored with no more than four colors. We’ll talk about later – it’s the first computer assisted proof that I’m aware of.
But for now, back to vertex coloring. How can we find the chromatic number of an arbitrary graph, G (also written χ(G))?
The one that students often come up with as a first guess – is to find the vertex with highest degree, and that the degree of that vertex will be one smaller than the chromatic number. Alas, it’s not so easy. Take a look at the graph to the right: the maximum degree of a vertex is 4, but it can be 2-colored.
Another common idea is that the chromatic number should be the size of the smallest clique in the graph. Again, no dice – look at the example to the right: the largest clique has degree four, but the graph needs 5 colors. But the largest clique *is* a lower bound.
What we end up with isn’t particularly pretty. There’s no simple way of finding the minimum coloring of a graph. What there *is* is a method of figuring it out from pieces using the lowering bound provided by the the largest clique. It’s based on the idea of a *critical subgraph*.
A critical subgraph C of a graph G is a *proper* subgraph of G – that is, a subgraph of G where C≠G – such that for every proper subgraph B of C, χ(B)<&chi(C). So we can *reduce* G to its largest critical subgraph – and the chromatic number of that subgraph is the same as the chromatic number of G.
So we’ve reduced the problem to identifying the largest critical subgraph. There are a couple of useful properties that can help us:
1. Critical subgraphs are always connected. This should be pretty obvious – if the graph
isn’t connected, then you can color the disconnected subgraphs separately, which
would mean that it’s not critical.
2. In a critical subgraph C with chromatic number χ(C), every node
will have minimum degree χ(C)-1.
But aside from those, we’re mostly on our own. And just to be spiteful, graph colorings also have a nasty property.
Suppose you have a graph G. The number of edges in the smallest cycle in G is called the *girth* of G.
For any x,y≥2, there is a graph with girth x, and chromatic number y. What that means is that you can’t do things like rely on cliques, even as an approximation. Because, for example, a graph with chromatic number 300 isn’t even guaranteed to contain any cliques of size three! Because a 3-clique is a triangle, which is a cycle of size 3… But there are graphs with chromatic number 300, and girth 50.
Just for an example of a graph with this kind of property: the figure to the right is called the Grötzcsh graph. It’s got girth four, but it contains no triangles at all. Try and figure out how many colors it needs.
*chews thoughtfully on its Crayola*
see this is why i’m not a maths major.
Lepht
I count 10 total colors.
Start with center vertex as color 1.
The next ring of vertices have to be colors 2-6 due to multiple connections to and from the outer ring.
The outer ring would then have colors 7, 8, 9, 10 and one of color 1.
Wow. My calculations went from a starting number of 4 colors and grew quickly as I started eliminating previously unseen two-same-adjacent color assignments.
Aaaand I just realized the last outer vertex can’t be color 1, but a different color 11, thus taking the total to 11 colors, or one for each vertex.
Egad!
4 colors was correct. Starting with the center vertex as color 1, the next ring of vertices can all be one color. Since they are all adjacent to the center, it has to be a 2nd color. For the outer ring, you can reuse the first color for 2 vertices. The remaining 3 vertices need 2 colors.
Although, this only proves the chromatic number is no greater than 4, not that it is equal to 4.
Hehe, I was for some reason adding a separate rule that I don’t know WHERE the heck it came from; specifically, that no color can be adjacent to two vertices which are the same color as each other.
Silly me. So, my initial intuition WAS right at 4 colors.
If I’m reading the problem right, then four colors is enough.
The center vertex is color 1.
For the inner ring, each vertex is connected to the center vertex and to two vertices in the outer ring, but not to any other vertex in the inner ring. Thus there is no reason why these five vertices cannot have the same color, which would be color 2.
Each vertex in the outer ring is connected to its two neighbors on the outer ring and to the corresponding two vertices of the inner ring, but not to the center vertex. Thus three colors are needed for the outer ring, one of which can be the same as the center vertex. This gives colors 1, 3, and 4.
If I’m wrong, what am I overlooking?
Speaking of which…
The problem is not showing that 4 colors are enough. Merely coloring the graph demonstrates that. The problem is showing that 3 colors aren’t enough. That is a somewhat tougher problem.
“There’s two versions of it, vertex coloring, and face coloring.”
Well, actually, there’s another one… edge coloring, of course, namely coloring the edges of the graph so that adjacent edges (those sharing a vertex) are colored differently.
The edge-chromatic number of a graph has some peculiar and unintuitive properties, primarily Vizing’s theorem: Given a simple graph G with maximum degree D, the graph can be edge-colored with D or D+1 colors. So all graphs fall into just two categories, usually called “class 1” and “class 2” (terrible nomenclature). Determining the class of a graph is, surprise surprise, NP-complete, so the edge-coloring problem still qualifies as “hard” even though it’s so limited in options.
(PS Welcome to Google! I’m 1.5 months more veteran than you so I get to say that.)
It’s probably worth noting that the 4 color theorem not only proves that any planar graph can be face-colored with at most 4 colors. But also (using the geometric dual of the graph) it can be vertex colored in at most 4 colors as well.
Also the second picture (the one with the 4-clique) is planar, so you _can_ do it in 4 colors, (notice the node colored green on the far left. You can change that to yellow, the blue one to green, and the white one to blue.)
~~Joe
What do you know – there is a mapping from graphs to maps. Sweet!
And now I see why cliques are interesting.
The possible connection between graph coloring and spin structures is intriguing, even if it will turn out to be a remote one.
Unfortunately, I’m not sure if it makes spin more or less understandable. 🙂
Egad! I played a few levels of the graph game an earlier post linked to for kicks, and I believe I can see the planarity directly now, which I don’t think I would otherwise. And they say that gaming and math are harmless occupations…
@ Torbjorn (modulo fancy ‘o’ character)
Heh, I love that game, I played it every day when I was supposed to be paying attention in Graph Theory Class…
🙂
Assume that three colours are sufficient, and start with the outer ring. Using three colours they can be labelled 1, 2, 1, 2, 3 as you go round the ring – that’s the only possible pattern. The outer ring colour 3 is connected to two vertices, one of which is connected to an outer 1, and the other to an outer 2. Thus the inner ring must contain both colours 1 and 2. Now there is an inner ring vertex connected to both vertices on either side of the outer 3, and these vertices have differing colours 1 and 2 – so that the inner ring vertex here must have colour 3. So the inner ring has all three colours, which are all connected to the central vertex, which therefore can not be coloured with any of the three colours. We can conclude that the assumption that three colours is sufficient is incorrect.
To be clearer, I should have worded this bit as: “The outer ring colour 3 is connected to two inner ring vertices”. The reasoning is easier to see when you draw it!
If you replace the blue with a yellow and the topmost yellow with a green, surely the second graph can be coloured with just 4 colours?
When it comes to graph coloring, my favorite connection is the one to Zero knowledge proofs: the protocol is really nice and easy to understand. Might be something to bring up as a tangent to graphs.
On the space chromatic number
Source Discrete Mathematics archive
Volume 256 , Issue 1-2 (September 2002)
Pages: 499 – 507
Year of Publication: 2002
ISSN:0012-365X
Author
Oren Nechushtan
Department of Computer Science, Tel Aviv University, Ramat Aviv, 69978 Tel Aviv, Israel
Publisher
Elsevier Science Publishers B. V. Amsterdam, The Netherlands, The Netherlands
Additional Information:
DOI Bookmark: 10.1016/S0012-365X(00)00406-4
ABSTRACT
The chromatic number of the space is the minimum number of colors needed to color all points of the Euclidean space so that no two points of the same color are at unit distance. We show that this number is at least 6, improving the best-known previous bound of 5.
———-
Axiom of choice and chromatic number of Rn
Source Journal of Combinatorial Theory Series A archive
Volume 110 , Issue 1 (April 2005)
Pages: 169 – 173
Year of Publication: 2005
ISSN:0097-3165
Author
Alexander Soifer
Princeton University, Mathematics, DIMACS, Rutgers University, Piscataway NJ and University of Colorado at Colorado Springs, 1420 Austin Bluffs Parkway, Colorado Springs, CO
Publisher
Academic Press, Inc. Orlando, FL, USA
DOI Bookmark: 10.1016/j.jcta.2004.10.004
ABSTRACT
In previous papers (J. Combin Theory Ser. A 103 (2003) 387) and (J. Combin. Theory Ser. A 105 (2004) 359) Saharon Shelah and I formulated a conditional chromatic number theorem, which described a setting in which the chromatic number of the plane takes on two different values depending upon the axioms for set theory. We also constructed examples of a distance graph on the real line R and difference graphs on the real plane R2 whose chromatic numbers depend upon the system of axioms we choose for set theory. Ideas developed there are extended in the present paper to construct difference graphs on the real space Rn, whose chromatic number is a positive integer in the Zermelo-Fraenkelchoice system of axioms, and is not countable (if it exists) in a consistent system of axioms with limited choice, studied by Solovay (Ann. Math. Ser. 2 (1970) 1). These examples illuminate how heavily combinatorial results can depend upon the underlying set theory, help appreciate the potential complexity of the chromatic number of n-space problem, and suggest that the chromatic number of n-space may depend upon the system of axioms chosen for set theory.
It would take 3 colors to do the outermost ring. No two adjacent ones could be the same color, but alternating ones could. Thus, we could have 2 sets of 2 with the same color and an odd one out.
The inner ring you can make the same color as the outer ring. Since the nearest vertex is not connected, it can be the same color. This is an arbitrary choice, because one will have the option to be two different colors, but only one.
The center vertex has to be a different color of them all.
Thus, it would take 4 colors. You can arrange the four in a number of ways, but it seems like for is the minimum.
—
I believe you are correct about the 4 color problem being the first proven via computer. They did it the rough and tumble way of proving this by exploring all possible scenarios which are finite but a very large number. I believe there are people who are looking for a more elegant proof…
Your second graph coloring example can be 4-colored, it doesn’t require 5 as stated. Change left-most green to white, and blue to green.
Thanks for another interesting article btw.