A bivariate chromatic polynomial for signed graphs

DOI10.1007/S00373-014-1481-6zbMATH Open1327.05099arXiv1204.2568OpenAlexW1991911469MaRDI QIDQ497310FDOQ497310

Authors: Matthias Beck, Mela Hardin 

Publication date: 24 September 2015

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

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.

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

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

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)

Cites Work

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

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)