Abstract:Introduced by Birkhoff in 1912 to study the four-color conjecture, the chromatic polynomial has become one of the most extensively studied graph polynomials. It is closely connected to the Tutte polynomial through specialization, to the characteristic polynomial of the associated graphic matroid, and to the flow polynomial through planar duality. It has also inspired several related polynomials, including the $\sigma$-polynomial, the $w$-polynomial, and the $\tau$-polynomial. This survey examines these relationships, illustrated in Figure 1, and reviews the main results.
From: Fengming Dong [view email]
[v1]
Fri, 10 Jul 2020 07:42:36 UTC (64 KB)
[v2]
Thu, 16 Jul 2020 03:46:35 UTC (89 KB)
[v3]
Fri, 11 Sep 2026 06:17:54 UTC (58 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。