CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS

DOI10.24330/IEJA.969651zbMATH Open1487.16036arXiv1611.04303OpenAlexW3182596043MaRDI QIDQ5164818FDOQ5164818

Authors: Loïc Foissy 

Publication date: 15 November 2021

Published in: International Electronic Journal of Algebra (Search for Journal in Brave)

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 polynomi-als. We also give non-commutative version of this construction, replacing graphs by indexed graphs and Q[X] by the Hopf algebra WSym of set partitions.

Full work available at URL: https://arxiv.org/abs/1611.04303

Recommendations

• scientific article; zbMATH DE number 568845
• scientific article; zbMATH DE number 833904
• Chromatic polynomials of complements of bipartite graphs
• scientific article; zbMATH DE number 4095494
• Chromatic polynomials of graphs from Kac-Moody algebras
• On chromatic polynomials of some kinds of graphs
• On chordal graphs and their chromatic polynomials
• Chromatic polynomials of hypergraphs
• Chromatic polynomials of hypergraphs
• scientific article; zbMATH DE number 3843776

zbMATH Keywords

chromatic polynomialchromatic symmetric functionbialgebras in cointeraction

Mathematics Subject Classification ID

Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Connections of Hopf algebras with combinatorics (16T30)

Cites Work

• Title not available (Why is that?)
• A symmetric function generalization of the chromatic polynomial of a graph
• Title not available (Why is that?)
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Renormalization in quantum field theory and the Riemann-Hilbert problem. I: The Hopf algebra structure of graphs and the main theorem
• Acyclic orientations of graphs
• Monoidal functors, species and Hopf algebras
• Title not available (Why is that?)
• Title not available (Why is that?)
• Commutative combinatorial Hopf algebras.
• Noncommutative symmetric functions
• Duality between quasi-symmetric functions and the Solomon descent algebra
• Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables
• Hopf algebras, renormalization and noncommutative geometry
• Incidence Hopf algebras
• Title not available (Why is that?)
• A chromatic symmetric function in noncommuting variables
• Combinatorial Hopf algebras and generalized Dehn–Sommerville relations
• Symmetric functions, noncommutative symmetric functions and quasisymmetric functions. II.
• The incidence Hopf algebra of graphs.
• Chromatic Polynomials
• On bialgebras and Hopf algebras of oriented graphs.
• Two interacting Hopf algebras of trees: a Hopf-algebraic approach to composition and substitution of B-series.
• Commutative and non-commutative bialgebras of quasi-posets and applications to Ehrhart polynomials
• Word symmetric functions and the Redfield-P\'olya
• MacMahon symmetric functions, the partition lattice, and Young subgroups.

Cited In (16)

• Chromatic polynomials of graphs from Kac-Moody algebras
• Holomorphic quadratic differentials on graphs and the chromatic polynomial
• An extension of the bivariate chromatic polynomial
• On chromatic functors and stable partitions of graphs
• Canonical characters on simple graphs.
• Chromatic symmetric function of graphs from Borcherds algebras
• Eight times four bialgebras of hypergraphs, cointeractions, and chromatic polynomials
• The Fortuin-Kasteleyn polynomial as a bialgebra morphism and applications to the Tutte polynomial
• On a Hopf algebra in graph theory
• Title not available (Why is that?)
• The kernel of chromatic quasisymmetric functions on graphs and hypergraphic polytopes
• Chromatic polynomials and representations of the symmetric group
• Bijective proofs of proper coloring theorems
• Chromatic graph homology for brace algebras
• New invariants for permutations, orders and graphs
• An attempt to classify bipartite graphs by chromatic polynomials

This page was built for publication: CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5164818)