Tag Archives: coloring

December 2, 2010

The chromatic number of Christmas tree is 4: on graph coloring problems over the holiday

I enjoy the holiday season. I unashamedly celebrate Christmas, and I enjoy decorating the house for the holidays. This year, I used graph coloring problems to help me decorate. If you are not familiar with graph coloring, consider a graph with a set of vertices and edges. The goal is to assign a color to each vertex such that no two connected vertices have the same color and such that the fewest number of colors are used (the chromatic number). One application is to create maps, such as this one of the United States.

How does graph coloring relate to Christmas decorating? I’ll give you an example. I have had an intense desire for the past 17 years or so to decorate my Christmas tree using only a few, beautifully coordinated colors (like red/silver/gold or purple/silver) rather than throw on a bunch of ornaments of every color like I always do. But I’d decorate the tree OR style, by hanging exactly one ornament on each branch and requiring that adjacent branches have different colors. This in essence imposes a graph coloring problem on my tree decorating. The chromatic number of a planar graph is 4. I suppose that the chromatic number of a conic graph (i.e., a Christmas tree) is also four, since a conic graph can be cut along one side to become a plane. I am not sure if the edges removed to turn the cone into a plane would be problematic, but I doubt it (graph theorists, please leave a comment!).

The reason I have never colored my Christmas tree is that I am sentimental and feel the need to hang all of my favorite ornaments on the tree, regardless of their color. With young kids who create a few new ornaments every year of various colors that don’t fit any of my Christmas tree decorating fantasies, I always thought that I would never color my Christmas tree in the near-future. Or so I thought.

This year, I bought a Christmas tree-shaped centerpiece that requires a gumdrop to be placed on the end of each branch (it is pictured below, along with my Christmas tree). I examined the centerpiece, and noticed that all of the branches lie in a vertical line, which should allow me to use as few as two colors. I opted for three (red, green, white), but my daughters insisted on using purple, too. The best part was when I explained the concept to my six year old, and she was really jazzed by the extra challenge (a future graph theorist?) When the tree was four-colored, my ~3-year old added a few yellow and orange gumdrops to some of the extra branches, so now the tree has six colors. But I think there’s a good chance that she will eat the yellow and orange gumdrops at some point, bringing the tree back to four colors as we had originally intended.

On a related note, I once had a conversation about vertex coloring over a bag of Valentine M&Ms. Valentine M&Ms have four colors whereas holiday M&Ms have three colors, and if you’re eating M&Ms with another nerd, it eventually leads to a discussion of the types of graphs whose chromatic numbers are equal to the number of M&M colors. I suppose this is the type of problem one nerd has if they eat candy with another nerd, but it’s a good problem to have.

This blog post contributes to the INFORMS monthly blogging theme. Look for the INFORMS blog to summarize the blogs at the end of the month.

What are your favorite graph coloring results?