Lower bounds and properties for the average number of colors in the non-equivalent colorings of a graph

DOI10.1016/J.DAM.2022.08.011MaRDI QIDQ6046133zbMATH OpenOpenAlexFDO

Authors Alain Hertz, Hadrien Mélot, Sébastien Bonte, Gauvain Devillez

Publication date 15 May 2023

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

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

zbMATH Keywords

average number of colorsgraph coloringgraphical Bell numbers

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Bell and Stirling numbers (11B73)

Abstract: We study the average number $mathcalA(G)$ of colors in the non-equivalent colorings of a graph $G$. We show some general properties of this graph invariant and determine its value for some classes of graphs. We then conjecture several lower bounds on $mathcalA(G)$ and prove that these conjectures are true for specific classes of graphs such as triangulated graphs and graphs with maximum degree at most 2.

Recommendations

• Upper bounds on the average number of colors in the non-equivalent colorings of a graph
• Neighbor sum distinguishing colorings of graphs with maximum average degree less than \(\frac{37} {12}\)
• A sharp lower bound on the number of non-equivalent colorings of graphs of order \(n\) and maximum degree \(n - 3\)
• Counting the number of non-equivalent vertex colorings of a graph
• On equitable -coloring of graphs with low average degree

Cites work

• A sharp lower bound on the number of non-equivalent colorings of graphs of order \(n\) and maximum degree \(n - 3\)
• Bell and Stirling numbers for disjoint unions of graphs
• Bell and Stirling numbers for graphs
• Counting the number of non-equivalent vertex colorings of a graph
• Facet defining inequalities among graph invariants: The system graphedron
• Graph theory
• scientific article; zbMATH DE number 7471007 (Why is no real title available?)
• scientific article; zbMATH DE number 7114889 (Why is no real title available?)
• scientific article; zbMATH DE number 2199828 (Why is no real title available?)
• On rigid circuit graphs
• On the number of distinct block sizes in partitions of a set
• Stirling numbers of forests and cycles
• Stirling numbers of the second kind and Bell numbers for graphs

Cited in

(8)

• Bounds for mean colour numbers of graphs
• Lower bounds on strip discrepancy for nonatomic colorings
• A sharp lower bound on the number of non-equivalent colorings of graphs of order \(n\) and maximum degree \(n - 3\)
• Counting the number of non-equivalent vertex colorings of a graph
• Further results on the lower bounds of mean color numbers
• Removing Edges Can Increase the Average Number of Colours in the Colourings of a Graph
• scientific article; zbMATH DE number 6423760 (Why is no real title available?)
• Upper bounds on the average number of colors in the non-equivalent colorings of a graph

This page was built for publication: Lower bounds and properties for the average number of colors in the non-equivalent colorings of a graph

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