Beyond Counting Graph Colorings with Sara Krehbiel, Santa Clara University

The graph coloring problem requires that neighboring vertices in a graph always have different colors. This models constraint satisfaction problems like the scheduling problem, in which several events (vertices) must be scheduled (colored) such that events with overlapping participants may not occur at the same time. For a given graph G and a fixed number of colors k, we can build another called a coloring graph, whose vertices are the colorings of G, with edges between pairs of colorings that differ on a single vertex of G. I will first present a well known result that the number of ways to color G using at most k colors is always polynomial in k. This chromatic polynomial counts the number of vertices in a coloring graph. But how many edges are there? How many in any other induced subgraph? I will outline some of the ideas behind a new result that these quantities are also polynomial in k, with a special focus on trees.