Bivariate order polynomials

DOI10.1007/S00373-019-02128-WMaRDI QIDQ2191257zbMATH OpenOpenAlexFDO

Authors Matthias Beck, Maryam Farahmand, Gina Karunaratne, Sandra Zuniga Ruiz

Publication date 24 June 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

acyclic orientationcombinatorial reciprocity theorembivariate chromatic polynomialorder preserving mapbivariate order polynomial

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Combinatorics of partially ordered sets (06A07)

Abstract: Motivated by Dohmen-P"onitz-Tittmann's bivariate chromatic polynomial $ch{i}_G(x,y)$, which counts all $x$-colorings of a graph $G$ such that adjacent vertices get different colors if they are $ley$, we introduce a bivarate version of Stanley's order polynomial, which counts order preserving maps from a given poset to a chain. Our results include decomposition formulas in terms of linear extensions, a combinatorial reciprocity theorem, and connections to bivariate chromatic polynomials.

Recommendations

• A bivariate chromatic polynomial for signed graphs
• Bivariate chromatic polynomials in computer algebra
• New expressions for order polynomials and chromatic polynomials
• An extension of the bivariate chromatic polynomial
• Generalized chromatic polynomials

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 2038883 (Why is no real title available?)
• scientific article; zbMATH DE number 3341135 (Why is no real title available?)
• A bivariate chromatic polynomial for signed graphs
• Acyclic orientations of graphs
• An extension of the bivariate chromatic polynomial
• Closed-form expansions for the universal edge elimination polynomial
• Fibonacci Identities and Graph Colorings

Cited in

(5)

• Bivariate chromatic polynomials of mixed graphs
• Arithmetic of marked order polytopes, monotone triangle reciprocity, and partial colorings
• A bivariate chromatic polynomial for signed graphs
• Bivariate chromatic polynomials in computer algebra
• Bivariables and Vénéreau polynomials

This page was built for publication: Bivariate order polynomials

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