Unlabeled signed graph coloring

DOI10.1216/RMJ-2019-49-4-1111MaRDI QIDQ2323915zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 13 September 2019

Published in Rocky Mountain Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.07730, https://projecteuclid.org/euclid.rmjm/1567044030

zbMATH Keywords

signed permutationsigned chromatic polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Abstract: We extend the work of Hanlon on the chromatic polynomial of an unlabeled graph to define the unlabeled chromatic polynomial of an unlabeled signed graph. Explicit formulas are presented for labeled and unlabeled signed chromatic polynomials as summations over distinguished order-ideals of the signed partition lattice. We also define the quotient of a signed graph by a signed permutation, and show that its signed graphic arrangement is closely related to an induced arrangement on a distinguished subspace. Lastly, a formula for the number of unlabeled acyclic orientations of a signed graph is presented which recalls classical reciprocity theorems of Stanley and Zaslavsky.

Recommendations

• The chromatic polynomial of an unlabeled graph
• A bivariate chromatic polynomial for signed graphs
• The odd-valued chromatic polynomial of a signed graph
• scientific article; zbMATH DE number 749258
• The chromatic polynomials of signed Petersen graphs

Cites work

• scientific article; zbMATH DE number 3379174 (Why is no real title available?)
• Acyclic orientations of graphs
• Characteristic polynomials of subspace arrangements and finite fields
• Inside-out polytopes
• Orientation of signed graphs
• Signed graph coloring
• The Geometry of Root Systems and Signed Graphs
• The chromatic polynomial of an unlabeled graph

Cited in

(5)

• A bivariate chromatic polynomial for signed graphs
• The odd-valued chromatic polynomial of a signed graph
• An extension of Stanley's symmetric acyclicity theorem to signed graphs
• Nowhere-harmonic colorings of graphs
• The chromatic polynomial of an unlabeled graph

This page was built for publication: Unlabeled signed graph coloring

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