A bivariate chromatic polynomial for signed graphs

DOI10.1007/S00373-014-1481-6MaRDI QIDQ497310zbMATH OpenOpenAlexFDO

Authors Matthias Beck, Mela Hardin

Publication date 24 September 2015

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

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

zbMATH Keywords

signed graphdeletion-contractionacyclic orientationinside-out polytopebivariate chromatic polynomialcombinatorial reciprocitygraphic arrangement

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Lattice points in specified regions (11P21)

Abstract: We study Dohmen--P"onitz--Tittmann's bivariate chromatic polynomial $c_{G}amma(k,l)$ which counts all $(k+l)$-colorings of a graph $Gamma$ such that adjacent vertices get different colors if they are $lek$. Our first contribution is an extension of $c_{G}amma(k,l)$ to signed graphs, for which we obtain an inclusion--exclusion formula and several special evaluations giving rise, e.g., to polynomials that encode balanced subgraphs. Our second goal is to derive combinatorial reciprocity theorems for $c_{G}amma(k,l)$ and its signed-graph analogues, reminiscent of Stanley's reciprocity theorem linking chromatic polynomials to acyclic orientations.

Recommendations

• Tutte's dichromate for signed graphs
• Bivariate order polynomials
• Unlabeled signed graph coloring
• The odd-valued chromatic polynomial of a signed graph
• Bivariate chromatic polynomials in computer algebra

Cites work

• scientific article; zbMATH DE number 3163858 (Why is no real title available?)
• scientific article; zbMATH DE number 3604927 (Why is no real title available?)
• scientific article; zbMATH DE number 2038883 (Why is no real title available?)
• A mathematical bibliography of signed and gain graphs and allied areas
• Acyclic orientations of graphs
• An extension of the bivariate chromatic polynomial
• Computing the Continuous Discretely
• Fibonacci Identities and Graph Colorings
• Inside-out polytopes
• Note on the decomposition of \(\lambda K_{m,n}\) (\(\lambda K^*_{m,n}\)) into paths
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Orientation of signed graphs
• Signed graph coloring

Cited in

(14)

• Unlabeled signed graph coloring
• Bivariate order polynomials
• Chromatic polynomials of signed book graphs
• The odd-valued chromatic polynomial of a signed graph
• A Tutte polynomial for signed graphs
• Bivariate chromatic polynomials of mixed graphs
• Nowhere-harmonic colorings of graphs
• Euler characteristic reciprocity for chromatic, flow and order polynomials
• The canonical Tutte polynomial for signed graphs
• Alternating signed bipartite graphs and difference-1 colourings
• Signed \(a\)-polynomials of graphs and Poincaré polynomials of real toric manifolds
• The chromatic polynomials of signed Petersen graphs
• Bivariate chromatic polynomials in computer algebra
• Tutte's dichromate for signed graphs

This page was built for publication: A bivariate chromatic polynomial for signed graphs

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