**Problem of the Week**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

**Math Club**

**Actuarial Association**

You are here: Homepage » Seminars - Academic year 2023-24 » Combinatorics Seminar » Bruce Sagan (Michigan State)

seminars:comb:abstract.200402sagc

Let G be a combinatorial graph with vertex set V and edge set E. A ``proper coloring'' of G is a function c from V to {1,2,…n} such that if uv is an edge then c(u) does not equal c(v). This is the same restriction as in the famous Four Color Theorem. In 1912, G. D. Birkhoff showed that the number of proper colorings is a polynomial in n, called the chromatic polynomial P(G,n), which has many wonderful properties. More recently, Stanley showed that one can associate with G a symmetric function X(G,x) which reduces to P(G,n) under specialization of the variable set x. But P(G,n) satisfies a deletion-contraction law which is useful for inductive proofs of its properties, while X(G,x) does not. We will show how one can derive such a law using symmetric functions in noncommuting variables and give applications.

I will not assume any background about graph coloring or symmetric functions.

This is joint work with David Gebhard.

seminars/comb/abstract.200402sagc.txt · Last modified: 2020/01/29 14:03 (external edit)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported