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:
As far as I know, this function xG, k(n) has not been studied before, so none of these questions have known answers.