Unlabeled signed graph coloring

DOI10.1216/RMJ-2019-49-4-1111zbMATH Open1419.05097arXiv1511.07730OpenAlexW2970705727MaRDI QIDQ2323915FDOQ2323915

Authors: Yanyan Li 

Publication date: 13 September 2019

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

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.

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

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

zbMATH Keywords

signed permutationsigned chromatic polynomial

Mathematics Subject Classification ID

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

Cites Work

• Signed graph coloring
• Acyclic orientations of graphs
• Inside-out polytopes
• The Geometry of Root Systems and Signed Graphs
• Orientation of signed graphs
• Title not available (Why is that?)
• Characteristic polynomials of subspace arrangements and finite fields
• The chromatic polynomial of an unlabeled graph

Cited In (5)

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

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)