Chromatic polynomial とその変種

Hersh と Swartz [HS08] によると, グラフの chromatic polynomial は, Birkhoff により 1912年に導入されたらしい。 Chia による文献表 [Chi97] がある。Steingrimsson [Ste01] は, chromatic polynomial がある simplicial complexStanley-Reisner 環の ideal の Hilbert series として表わせることを示した。

  • chromatic polynomial
  • dichromatic polynomial
  • multivariate chromatic polynomial ([Whi11])

Stanley による symmetric function としての拡張 [Sta95] もある。 その refinement として Shareshian と Wachs [SW12; SW16] により chromatic quasisymmetric function が導入された。

  • chromatic symmetric function
  • chromatic quasisymmetric function

他に, Tutte [Tut49] が, 平面グラフに対し chromatic polynomial の dual となるべきものとして定義した flow polynomial というものもある。

  • flow polynomial

その変種としては, Chen と Stanley の [CS12] で考えられている modular flow polynomial とか integral flow polynomial といったものがある。

\(q\)-analogue は, Bajo と Beck と Vindas-Meléndez [BBV] により導入され調べられている。

  • \(q\)-chromatic polynomial

これらの多項式については, categorification も構成されている。

Abstract simplicial complex への一般化は, Cooper と de Silva と Sazdanovic [CSS19] により, graphic configuration space の一般化を用いて定義されている。

  • simplicial chromatic polynomial



Esme Bajo, Matthias Beck, and Andrés R. Vindas-Meléndez. \(q\)-Chromatic polynomials. arXiv: 2403.19573.


G. L. Chia. “A bibliography on chromatic polynomials”. In: Discrete Math. 172.1-3 (1997). Chromatic polynomials and related topics (Shanghai, 1994), pp. 175–191. url:


Beifang Chen and Richard P. Stanley. “Orientations, lattice polytopes, and group arrangements II: Modular and integral flow polynomials of graphs”. In: Graphs Combin. 28.6 (2012), pp. 751–779. arXiv: 1105.2677. url:


Andrew A. Cooper, Vin de Silva, and Radmila Sazdanovic. “On configuration spaces and simplicial complexes”. In: New York J. Math. 25 (2019), pp. 723–744.


Patricia Hersh and Ed Swartz. “Coloring complexes and arrangements”. In: J. Algebraic Combin. 27.2 (2008), pp. 205–214. arXiv: 0706.3657. url:


Richard P. Stanley. “A symmetric function generalization of the chromatic polynomial of a graph”. In: Adv. Math. 111.1 (1995), pp. 166–194. url:


Einar Steingrímsson. “The coloring ideal and coloring complex of a graph”. In: J. Algebraic Combin. 14.1 (2001), pp. 73–84. arXiv: math/ 0104063. url:


John Shareshian and Michelle L. Wachs. “Chromatic quasisymmetric functions and Hessenberg varieties”. In: Configuration spaces. Vol. 14. CRM Series. Ed. Norm., Pisa, 2012, pp. 433–460. arXiv: 1106.4287. url:


John Shareshian and Michelle L. Wachs. “Chromatic quasisymmetric functions”. In: Adv. Math. 295 (2016), pp. 497–551. arXiv: 1405. 4629. url:


W. T. Tutte. “On the imbedding of linear graphs in surfaces”. In: Proc. London Math. Soc. (2) 51 (1949), pp. 474–483. url:


Jacob A. White. “On multivariate chromatic polynomials of hypergraphs and hyperedge elimination”. In: Electron. J. Combin. 18.1 (2011), Paper 160, 17. arXiv: 1012.3423.