

























Let G be a combinatorial graph with vertices V and edges E. A proper coloring of G is an assignment of colors to the vertices such that no edge connects two vertices of the same color. These are the colorings considered in the famous Four Color Theorem. It turns out that the number of proper colorings of G using t colors is a polynomial in t, called the chromatic polynomial of G. This polynomial has many wonderful properties. It also has the surprising habit of appearing in contexts which, a priori, have nothing to do with graph coloring. We will survey three such instances involving acyclic orientations, hyperplane arrangements, and increasing forests. In addition, connections to symmetric functions and algebraic geometry will be mentioned.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。