Coloring graphs with polynomials

More chromatic hoonja-doonja!

Suppose you have a bunch of tokens of different colors and weights.  X_1 colors of weight 1 tokens, X_2 colors of weight 2 tokens, etc.

Let Γ be a graph.  A (weighted) b-coloring of Γ is an assignment to each vertex of a set of tokens with total weight b, such that adjacent vertices have no tokens in common.  Let χ_Γ(X_1, … X_b) be the number of b-colorings of Γ.  I made up this definition but I assume it’s in the literature somewhere.


First of all, χ_Γ(X_1, … X_b) is a polynomial.

Is this multivariable “chromatic polynomial” of any interest?  Well, here’s one place it comes up.  By a degree-b polynomial coloring of Γ we mean an assignment of a monic squarefree degree d polynomial in R[x] to each vertex of Γ, so that adjacent vertices are labeled with coprime polynomials.   Now let U_b(Γ) be the manifold parametrizing degree-b colorings of Γ.

Then the Euler characteristic of U_b(Γ) is χ_Γ(-1,1,0,…0).

I worked this out via the same kind of Lefschetz computation as in the previous post, but once you get the answer, you can actually derive this as a corollary of Stanley’s theorem.  And it was presumably already known.

By the way:  let V_n be the free vector space spanned by the b-colorings of Γ where all the tokens have weight 1; these are called fractional colorings sometimes.  Then S_n acts on V_n by permutation of colors.  The character of this action is a class function on S_n.  More precisely, it is

χ_Γ(X_1, … X_b)

where X_i is now interpreted as a class function on S_n, sending a permutation to the number of i-cycles in its cycle decomposition.  Of course the real thing going on behind the scenes is that the V_n form a finitely generated FI-module.

Tagged , , ,

6 thoughts on “Coloring graphs with polynomials

  1. Tom Church says:

    Is the FI-module V actually an FI#-module? Or should I assume that the last identity will fail in weird ways for small enough n?

  2. JSE says:

    The way I set it up makes it look like it’s just an FI-module, but, as John Wiltshire-Gordon explained to me, if you think of it as “colorings / inadmissible colorings” instead of “admissible colorings” it actually has the structure of Fin-module (Fin = category of finite sets with ALL maps) and that makes it (character) polynomial all the way down. (Or at least all the way down to n=1; now that I think about it, I don’t know whether that makes it obvious that it works at 0, maybe JWG will wander by and weigh in?)

  3. Nate says:

    A little late, but in a similar vein to thinking of it as “colorings / inadmissible colorings” you could also think of it as “partial colorings / partial colorings with non-full support” to get an FI#-module structure.

  4. JSE says:

    Wait can you explain this further? A partial coloring is…?

  5. Nate says:

    A partial coloring on a graph G is an assignment of colors to some of the vertices of G, subject to the usual condition that no two adjacent vertices receive the same color. You could also think of it as the data of a subset of the vertices of G (which I referred to as the support) and a usual coloring of the corresponding induced subgraph. Now we get an FI#-module by sending a finite set S to the vector space spanned by partial S-colorings of G, since now if a color doesn’t get sent anywhere by an FI#-map we can just uncolor any vertices that received that color. Inside this there is an FI#-submodule spanned by those partial colorings of non-full support, and the quotient corresponds to the usual colorings of G.

  6. JSE says:

    Awesome! That answers my question.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: