Bijective proofs of proper coloring theorems

DOI10.1080/00029890.2021.1901460MaRDI QIDQ4991610zbMATH OpenOpenAlexWikidataFDO

Authors Bruce E. Sagan, Vincent Vatter

Publication date 3 June 2021

Published in The American Mathematical Monthly (Search for Journal in Brave)

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

zbMATH Keywords

chromatic polynomialchromatic symmetric function

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31) Symmetric functions and generalizations (05E05)

Abstract: The chromatic polynomial and its generalization, the chromatic symmetric function, are two important graph invariants. Celebrated theorems of Birkhoff, Whitney, and Stanley show how both objects can be expressed in three different ways: as sums over all spanning subgraphs, as sums over spanning subgraphs with no broken circuits, and in terms of acyclic orientations with compatible colorings. We establish all six of these expressions bijectively. In fact, we do this with only two bijections, as the proofs in the symmetric function setting are obtained using the same bijections as in the polynomial case and the bijection for broken circuits is just a restriction of the one for all spanning subgraphs.

Recommendations

• Bijective proofs of two broken circuit theorems
• CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS
• Graph colorings and acyclic orientations
• The amazing chromatic polynomial
• A symmetric function generalization of the chromatic polynomial of a graph

Cites work

• A symmetric function generalization of the chromatic polynomial of a graph
• Acyclic orientations of graphs
• Algebraic Graph Theory
• An introduction to chromatic polynomials
• Bijective proofs of two broken circuit theorems
• Chromatic Polynomials
• Combinatorial reciprocity theorems
• Enumeration of Golomb rulers and acyclic orientations of mixed graphs
• Enumeration of Mixed Graphs
• Graph colorings and acyclic orientations
• Graphs with equal chromatic symmetric functions
• scientific article; zbMATH DE number 3547324 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• scientific article; zbMATH DE number 718851 (Why is no real title available?)
• Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
• On an algorithm for comparing the chromatic symmetric functions of trees
• On weak chromatic polynomials of mixed graphs
• Unimodality, log-concavity, real-rootedness and beyond

Cited in

(3)

• Bijective proofs of two broken circuit theorems
• The amazing chromatic polynomial
• A signed e-expansion of the chromatic quasisymmetric function

This page was built for publication: Bijective proofs of proper coloring theorems

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