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

DOI10.1016/J.DAM.2015.09.015MaRDI QIDQ260025zbMATH OpenOpenAlexFDO

Authors Alain Hertz, Hadrien Mélot

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

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

Recommendations

• 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
• Some new bounds for the maximum number of vertex colorings of a (v,e)-graph
• Lower bounds and properties for the average number of colors in the non-equivalent colorings of a graph
• scientific article; zbMATH DE number 4114659

Cites work

• \(\sigma\)-polynomials and graph coloring
• Bell and Stirling numbers for disjoint unions of graphs
• Bell and Stirling numbers for graphs
• Expansions of Chromatic Polynomials and Log-Concavity
• Facet defining inequalities among graph invariants: The system graphedron
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 2199828 (Why is no real title available?)
• Location of Zeros of Chromatic and Related Polynomials of Graphs
• Stirling numbers of forests and cycles
• Stirling numbers of the second kind and Bell numbers for graphs
• The boson normal ordering problem and generalized Bell numbers

Cited in

(7)

• A sharp lower bound on the number of non-equivalent colorings of graphs of order \(n\) and maximum degree \(n - 3\)
• Fubini numbers and polynomials of graphs
• scientific article; zbMATH DE number 7471007 (Why is no real title available?)
• 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
• Lexicographic unranking algorithms for the twelvefold way
• Enumerating some stable partitions involving Stirling and r-Stirling numbers of the second kind

Describes a project that uses

Uses Software

• OEIS
• GraPHedron

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

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