Counting the number of non-equivalent vertex colorings of a graph

DOI10.1016/j.dam.2015.09.015zbMath1332.05055OpenAlexW1418567529MaRDI QIDQ260025

Hadrien Mélot, Alain Hertz

Publication date: 18 March 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.09.015

zbMATH Keywords

chromatic polynomialgraphical Bell numbersnon-equivalent colorings

Mathematics Subject Classification ID

Graph polynomials (05C31) Extremal problems in graph theory (05C35) Bell and Stirling numbers (11B73) Coloring of graphs and hypergraphs (05C15)

Related Items (6)

A sharp lower bound on the number of non-equivalent colorings of graphs of order \(n\) and maximum degree \(n - 3\) ⋮ Upper bounds on the average number of colors in the non-equivalent colorings of a graph ⋮ Lower bounds and properties for the average number of colors in the non-equivalent colorings of a graph ⋮ Unnamed Item ⋮ Fubini numbers and polynomials of graphs ⋮ Enumerating some stable partitions involving Stirling and \(r\)-Stirling numbers of the second kind

Uses Software

• OEIS
• GraPHedron

Cites Work

• Facet defining inequalities among graph invariants: The system graphedron
• The boson normal ordering problem and generalized Bell numbers
• \(\sigma\)-polynomials and graph coloring
• Stirling numbers of forests and cycles
• Expansions of Chromatic Polynomials and Log-Concavity
• Location of Zeros of Chromatic and Related Polynomials of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Counting the number of non-equivalent vertex colorings of a graph