This is a continuation of yesterday’s blog Coloring Game! If you haven’t done so yet, please take the time to read it.
In the last post we discussed one of the games that is posed in graph theory, that is the four color theorem. For this problem the goal was to color a picture or a map in such a way that parts that shared a border didn’t share a color. In addition to maps, we can also look at coloring of graphs. A graph is collection of lines and points called edges and vertices, respectively. These are drawn in such a was that each edge has a point on each end, so we end up with something that looks like the example below.
In this example, we see that we have 16 edges and 8 vertices. Furthermore, we say that the degree of a vertex is the number of edges touching that vertex. Therefore, the degree of vertex 1 is 3.
Now, we have two games we can play. In the first game, our goal is to color the vertices each with a color so that no edge has the same color for both of its vertices. That is, if we move over a single edge, we should always arrive at a new color. Unlike the in the case of maps, we don’t have a nice theorem that states what the minimum number of colors is going to be. This means that even if we provide a coloring, we won’t know that we’ve used the minimum number of colors unless we look at special properties of the particular graph. As an example, we provide a vertex coloring with 4 colors below. We note that this must be the minimum number of colors used in this case because there are four vertices that all connect to each other.
If you’d like to create vertex coloring, you can draw any arbitrary graph and see what you come up with. Have fun drawing whatever shape you like.
The second coloring game we can play with graphs is to provide an edge coloring. In this situation, instead of coloring vertices, we color edges so that if any two edges meet at the same vertex, they cannot have the same color. As before, there is no nice way to know the minimum color needed for a general graph, so we have to look at these in a case by case basis. As an example, for the graph above we can have the following edge coloring with 5 colors. Note also that this is the minimum needed since there are vertices with degree 5.
An interesting case arises when we have a graph where every vertex has the same degree, say n, and the graph admits an n coloring. In this case, if we define having the same color as a relation on the edges, it will split the edges into sets of all the same color. Furthermore, each vertex touches exactly one edge of each color. Because of this, we can look at the color as a parallelism relation and treat the graph as a geometry. It is then further possible to take the set of points and the set of lines and define a multiplication on them in such way that we end up with an algebraic structure. We are then able to talk about colorings in a geometric or algebraic way giving us options when trying to find properties. Dr. Francis Pastijn and I actually explore this topic in a paper which is currently under review, so if you’d like more details on this, contact me.
I hope you have some fun with coloring.