Modified Chromatic Polynomials

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 x_G(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 x_G(1) = 0 whenever G has at least one edge. But since x_G(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 x_G(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 x_{G, 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: