Comps Insider: Haoyi Wang ’19

4 April 2019

Haoyi Wang

What is the title of your Comps?

Graph Colorings and the Four-Color Problem

What is your Comps topic?

In this project, I investigated problems that are equivalent to the famous 4-color problem, and the relationship between 3-edge colorings of graphs and the 4-color problem. In particular, I studied how the 4-face coloring is equivalent to bipartite dichotomy and the non-existence of irreducible graphs, how it can be reduced to a statement about 3-edge colorings of graphs, and how we can construct and prove the non-3-colorability of infinite families of snarks, or a connected bridgeless cubic graph, (which include the Petersen graph).

How many colors do we need to properly color the world map? Can you believe we only need four colors to do so? This is the famous 4-color problem. We can actually solve this problem using graph theory, where we color vertices instead of countries. 

Now, if we were to color the edges instead of vertices, how would the problem change? If each vertex is adjacent to three edges, are three colors enough to color all the edges so that two edges that are adjacent to the same vertex do not have the same color? Sadly, this is not always the case. In this presentation, I will talk about non-3-colorable graphs (snarks), how the famous 4-color problem and the 3-edge coloring problem are related, and how we can translate the 4-color problem into other interesting problems.

Why did you choose your Comps topic? 

I am a big fan of coloring books. After learning about graph colorings in a combinatorics class, I started to wonder if I could practice some of the theories on my favorite Pusheen coloring book. The 4-color problem seems an intriguing question. I tried to properly color the pages with only four colors, and it worked every time. Later, I encountered the Petersen graph when I was doing homework and realized that four colors are required to properly color its edges, which is a special case for the 3-edge coloring problem. Thus, I decided to work on infinite families of snarks, which include the Petersen graph as the base composition.

What was the most interesting article or piece of information that you found while researching your Comps?

It is really mind-blowing how Rufus Isaacs came up with two infinite families of snarks. Before him, mathematicians have long been searching for the non-trivial trivalent graphs that are not 3-edge colorable; however, only the Petersen graph and three other individual graphs (which were later proven to be in the same family of snarks that compose the Petersen graph with a similar structure by Isaacs) have been found. It is magnificent how mathematicians can connect many seemingly unrelated ideas. 

What was your Comps process like?

I spent the winter break reading two assigned papers from the department and searching for any related materials that could potentially help me understand the subject more in depth. In the first few weeks of winter term, I selected the final three papers that I want to focus on and started to closely analyze the information provided. This is one of the most interesting parts where I got the chance to think about some questions that are left as an exercise for readers in Isaacs’ paper; in particular, how can we construct the BDS Snarks and the Flower Snarks in a systematic way. After that, I began to work on summarizing the information and refining my presentation by choosing the appropriate graphs.

Why do you think it was  valuable for you to do your Comps project? 

This is a perfect opportunity to immerse myself in an interesting challenge. During the process, I honed basic researching skills, problem-solving skills, and presentation skills. Most important of all, by conquering the challenge, I feel more confident in doing more advanced mathematics.

Will you expand on your Comps in any way?

Absolutely. I plan to further investigate the double-star snark, its connections with the Petersen graph, and whether it is likely for a third infinite family of snarks to be found.

Here is the link to my COMPS!