论文标题
适当着色定理的徒证明
Bijective proofs of proper coloring theorems
论文作者
论文摘要
色多项式及其概括（色度对称函数）是两个重要的图形不变性。伯克霍夫（Birkhoff），惠特尼（Whitney）和斯坦利（Stanley）的著名定理展示了如何以三种不同的方式表达这两个物体：作为所有跨越子图的总和，作为跨越子图的总和没有损坏的电路，以及以兼容色彩的acyclic方向而言。我们将所有这六个表达式建立在远之间。实际上，我们只使用两种射击来完成此操作，因为使用与多项式情况相同的对称函数设置中的证明是获得的，而损坏的电路的两者只是对所有跨度子绘图的限制。
The chromatic polynomial and its generalization, the chromatic symmetric function, are two important graph invariants. Celebrated theorems of Birkhoff, Whitney, and Stanley show how both objects can be expressed in three different ways: as sums over all spanning subgraphs, as sums over spanning subgraphs with no broken circuits, and in terms of acyclic orientations with compatible colorings. We establish all six of these expressions bijectively. In fact, we do this with only two bijections, as the proofs in the symmetric function setting are obtained using the same bijections as in the polynomial case and the bijection for broken circuits is just a restriction of the one for all spanning subgraphs.
