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?**

**
**

Related posts: