论文标题
无环方向和签名图的色度多项式
Acyclic Orientations and the Chromatic Polynomial of Signed Graphs
论文作者
论文摘要
我们提出了无环方向和签名图（对称图）之间的新对应关系。 Goodall等人。引入了一个双变量色的多项式$χ_g（k，l）$，该$使用颜色$ 0，\ pm1，\ dots，\ pm k $以及$ l-1 $对称颜色$ 0_1，\ dots，0_ {l-1} $。我们表明，对双变量多项式$ |χ_g（-1,2）| $的评估等于签名的图形模量的无环方向数量，是通过交换源和下沉来产生的等效关系。我们提供了这一事实的三个证明，即使用感谢您的超平面布置的证明，使用删除 - 征服的证明以及直接证明。
We present a new correspondence between acyclic orientations and coloring of a signed graph (symmetric graph). Goodall et al. introduced a bivariate chromatic polynomial $χ_G(k,l)$ that counts the number of signed colorings using colors $0,\pm1,\dots,\pm k$ along with $l-1$ symmetric colors $0_1,\dots,0_{l-1}$. We show that the evaluation of the bivariate chromatic polynomial $|χ_G(-1,2)|$ is equal to the number of acyclic orientations of the signed graph modulo the equivalence relation generated by swapping sources and sinks. We present three proofs of this fact, a proof using toric hyperplane arrangements, a proof using deletion-contraction, and a direct proof.
