Chromatic polynomial とその変種

Hersh と Swartz [HS08] によると, グラフの chromatic polynomial は, Birkhoff により 1912年に導入されたらしい。 Chia による文献表 [Chi97] がある。Steingrimsson [Ste01] は, chromatic polynomial がある simplicial complex の Stanley-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 も構成されている。

• グラフ多項式の categorification

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

• simplicial chromatic polynomial

References

[BBV]

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

[Chi97]

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: http://dx.doi.org/10.1016/S0012-365X(97)90031-5.

[CS12]

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: http://dx.doi.org/10.1007/s00373-011-1080-8.

[CSS19]

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.

[HS08]

Patricia Hersh and Ed Swartz. “Coloring complexes and arrangements”. In: J. Algebraic Combin. 27.2 (2008), pp. 205–214. arXiv: 0706.3657. url: http://dx.doi.org/10.1007/s10801-007-0086-z.

[Sta95]

Richard P. Stanley. “A symmetric function generalization of the chromatic polynomial of a graph”. In: Adv. Math. 111.1 (1995), pp. 166–194. url: http://dx.doi.org/10.1006/aima.1995.1020.

[Ste01]

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: http://dx.doi.org/10.1023/A:1011222121664.

[SW12]

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: https://doi.org/10.1007/978-88-7642-431-1_20.

[SW16]

John Shareshian and Michelle L. Wachs. “Chromatic quasisymmetric functions”. In: Adv. Math. 295 (2016), pp. 497–551. arXiv: 1405. 4629. url: https://doi.org/10.1016/j.aim.2015.12.018.

[Tut49]

W. T. Tutte. “On the imbedding of linear graphs in surfaces”. In: Proc. London Math. Soc. (2) 51 (1949), pp. 474–483. url: https://doi.org/10.1112/plms/s2-51.6.474.

[Whi11]

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.