A sharp lower bound on the number of non-equivalent colorings of graphs of order \(n\) and maximum degree \(n - 3\)

DOI10.1016/j.dam.2016.06.025zbMath1376.05044DBLPjournals/dam/AbsilCHM18OpenAlexW2245479836WikidataQ60692141 ScholiaQ60692141MaRDI QIDQ1686044

Romain Absil, Hadrien Mélot, Alain Hertz, Eglantine Camby

Publication date: 20 December 2017

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

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

zbMATH Keywords

extremal theorynon-equivalent coloringsfixed maximum degreegraphical Bell number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Related Items (4)

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

Uses Software

• OEIS
• GraPHedron

Cites Work

• Counting the number of non-equivalent vertex colorings of a graph
• Facet defining inequalities among graph invariants: The system graphedron
• \(\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: A sharp lower bound on the number of non-equivalent colorings of graphs of order \(n\) and maximum degree \(n - 3\)