Modified Chromatic Polynomials

Michael P. Knapp

Chromatic polynomials are a standard topic in graph theory. In graph theory, a graph consists of dots (called vertices) and lines (called edges) which can connect the dots. There are two examples of graphs in the picture below.

For this project, an edge has to connect two different vertices, so there are no "loops" in the graph. Also, for this project, we will assume that two specific vertices are connected by at most one edge.

If you have a specific graph G, then a coloring of G is any way to assign a color to each vertex so that if two vertices are connected by an edge, then they have different colors. If the number of colors you use is n, then it is called an n-coloring. The chromatic polynomial of G, written as xG(n) tells you the total number of n-colorings of G that exist. (Actually, the notation for the chromatic polynomial is the Greek letter chi, and not the Roman letter x, but I don't know how to make a chi in html.)

Chromatic polynomials have many interesting properties. Perhaps the most interesting one is that it really is a polynomial in n. Also, it turns out that there is a pretty easy (although tedious) procedure that you can use to compute the chromatic polynomial of a graph. Finally, I'll mention one slightly more complicated property. Suppose that the graph G has at least one edge. Then it's impossible to color G using only one color (because the vertices connected by the edge would have the same color). This tells us that xG(1) = 0 whenever G has at least one edge. But since xG(n) is a polynomial, that means that it has n-1 as a factor. So this tells us that if G has at least one edge, then n-1 is a factor of xG(n).

In this project, I think that it would be interesting to study colorings where each color is only allowed to be used a certain number of times. So you could define a function xG, k(n) which tells you the number of ways to color the graph G using a total of n colors, where no colors are allowed to be used more than k times. You can ask several questions about this function which are similar to questions about chromatic polynomials. For example:

  • Is the function xG, k(n) still a polynomial?
  • Is there a nice procedure that we can use to calculate xG, k(n) for a specific graph?
  • Can we find formulas for xG, k(n) for "simple" families of graphs?
  • In the above questions, I've been assuming that k is fixed and that we're changing the value of n. What happens if you fix n and change the value of k?

    As far as I know, this function xG, k(n) has not been studied before, so none of these questions have known answers.