CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS

Abstract

The chromatic polynomial is characterized as the unique polynomial invariant of graphs, compatible with two interacting bialgebras structures: the first coproduct is given by partitions of vertices into two parts, the second one by a contraction-extraction process. This gives Hopf-algebraic proofs of Rota's result on the signs of coefficients of chromatic polynomials and of Stanley's interpretation of the values at negative integers of chromatic polynomials. We also consider chromatic symmetric functions and their noncommutative versions.

Keywords

• Bialgebras in cointeraction
• chromatic polynomial
• chromatic symmetric function

References

1. E. Abe, Hopf Algebras, Cambridge Tracts in Mathematics, vol. 74, Cambridge University Press, Cambridge-New York, 1980.
2. M. Aguiar, N. Bergeron, and F. Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compos. Math., 142(1) (2006), 1-30.
3. M. Aguiar and S. Mahajan, Monoidal Functors, Species and Hopf Algebras, CRM Monograph Series, vol. 29, American Mathematical Society, Providence, RI, 2010.
4. N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and coinvariants of the symmetric groups in noncommuting variables, Canad. J. Math., 60(2) (2008), 266-296.
5. G. Birkhoff and D. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc., 60 (1946), 355-451.
6. J.P. Bultel, A. Chouria and J.G. Luque, and O. Mallet, Word symmetric functions and the Redfield-Polya theorem, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Discrete Math.Theor. Comput. Sci. Proc., AS, Assoc. Discrete Math. Theor. Comput. Sci.,Nancy (2013), 563-574.
7. D. Calaque, K. Ebrahimi-Fard and D. Manchon, Two interacting Hopf algebras of trees: a Hopf-algebraic approach to composition and substitution of B-series, Adv. in Appl. Math., 47(2) (2011), 282-308.
8. A. Connes and D. Kreimer, Hopf algebras, renormalization and noncommutative geometry, Comm. Math. Phys., 199(1) (1998), 203-242.

9. A. Connes and D. Kreimer, Renormalization in quantum field theory and the Riemann-Hilbert problem. I. The Hopf algebra structure of graphs and the maintheorem, Comm. Math. Phys., 210(1) (2000), 249-273.
10. L. Foissy, Commutative and non-commutative bialgebras of quasi-posets and applications to Ehrhart polynomials, Adv. Pure Appl. Math., 10(1) (2019), 27-63.
11. D. Gebhard and B. Sagan, A chromatic symmetric function in noncommuting variables, J. Algebraic Combin., 13(3) (2001), 227-255.
12. I. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. Retakh and J.Y. Thibon, Noncommutative symmetric functions, Adv. Math., 112(2) (1995), 218-348.
13. F. Harary, Graph Theory, Addison-Wesley Publishing Co., Reading, Mass.- Menlo Park, Calif.-London, 1969.
14. M. Hazewinkel, Symmetric functions, noncommutative symmetric functions and quasisymmetric functions. II, Acta Appl. Math., 85(1-3) (2005), 319-340.
15. F. Hivert, J.C. Novelli and J.Y. Thibon, Commutative combinatorial Hopf algebras, J. Algebraic Combin., 28(1) (2008), 65-95.
16. B. Humpert and J. Martin, The incidence Hopf algebra of graphs, SIAM J. Discrete Math., 26(2) (2012), 555-570.
17. C. Kassel, Quantum Groups, Graduate Texts in Mathematics, vol. 155, Springer-Verlag, New York, 1995.
18. C. Malvenuto and C. Reutenauer, Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, 177(3) (1995), 967-982.
19. D. Manchon, On bialgebras and Hopf algebras or oriented graphs, Confluentes Math., 4(1) (2012), 1240003 (10 pp).
20. D. Manchon, A review on comodule-bialgebras, The Proceedings of the 2016 Abel Symposium "Computation and Combinatorics in Dynamics, Stochastics and Control", Abel Symp., Springer, Cham, 13 (2018), 579-597.
21. J.C. Novelli and J.Y. Thibon, Polynomial realizations of some trialgebras, ,in: Formal Power Series and Algebraic Combinatorics (FPSAC), San Diego, California, 2006.
22. M. Rosas, MacMahon symmetric functions, the partition lattice, and Young subgroups, J. Combin. Theory Ser. A, 96(2) (2001), 326-340.
23. G.C. Rota, On the foundations of combinatorial theory. I. Theory of Mobius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 2 (1964), 340-368.
24. W. Schmitt, Incidence Hopf algebras, J. Pure Appl. Algebra, 96(3) (1994), 299-330.
25. R. Stanley, Acyclic orientations of graphs, Discrete Math., 5 (1973), 171-178.
26. R. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math., 111(1) (1995), 166-194.
27. R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1999.
28. M. Sweedler, Hopf Algebras. Mathematics Lecture Note Series, W. A. Benjamin, Inc., New York, 1969.
29. P. van der Laan, Operads - Hopf algebras and coloured Koszul duality, Ph.D.- thesis, Universiteit Utrecht, 2004.