Upper Bounds on the Average Number of Colors in the Non-equivalent Colorings of a Graph

[en] A coloring of a graph is an assignment of colors to its vertices such that adjacent vertices have different colors. Two colorings are equivalent if they induce the same partition of the vertex set into color classes. Let A(G) be the average number of colors in the non-equivalent colorings of a graph G. We give a general upper bound on A(G) that is valid for all graphs G and a more precise one for graphs G of order n and maximum degree Δ (G) ∈ { 1 , 2 , n- 2 }.

Disciplines :

Mathematics

Author, co-author :

Hertz, Alain ; Department of Mathematics and Industrial Engineering, Polytechnique Montréal-Gerad, Montréal, Canada

Mélot, Hadrien ; Université de Mons - UMONS > Faculté des Science > Service Algorithmique

Bonte, Sébastien ; Université de Mons - UMONS > Faculté des Science > Service des Systèmes d'information

Devillez, Gauvain ; Université de Mons - UMONS > Faculté des Science > Service Algorithmique

Hauweele, Pierre ; Université de Mons - UMONS > Faculté des Science > Service Algorithmique

Language :

English

Title :

Upper Bounds on the Average Number of Colors in the Non-equivalent Colorings of a Graph

Publication date :

15 April 2023

Journal title :

Graphs and Combinatorics

ISSN :

0911-0119

Publisher :

Springer

Volume :

Issue :

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://link.springer.com/content/pdf/10.1007/s00373-023-02637-9.pdf

Research unit :

S825 - Algorithmique

Research institute :

Complexys
Infortech

Funders :

Fonds De La Recherche Scientifique - FNRS

Funding text :

Computational resources have been provided by the Consortium des Équipements de Calcul Intensif (CÉCI), funded by the Fonds de la Recherche Scientifique de Belgique (F.R.S.-FNRS) under Grant No. 2.5020.11 and by the Walloon Region.

Available on ORBi UMONS :

since 14 January 2024

Statistics

Number of views

6 (0 by UMONS)

Number of downloads

25 (1 by UMONS)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenAlex citations

Bibliography

Absil, R., Camby, E., Hertz, A., and Mélot, H.: A sharp lower bound on the number of non-equivalent colorings of graphs of order n and maximum degree n-3. Discrete Appl. Math. 234, 3–11 (2018). (Special Issue on the Ninth International Colloquium on Graphs and Optimization (GO IX), 2014)
Devillez, G., Hauweele, P., Mélot, H.: PHOEG Helps to Obtain Extremal Graphs. In: Fortz, B., Labbé, M. (eds) Operations Research Proceedings 2018 (GOR (Gesellschaft fuer Operations Research e.V.)) (sept. 12–14 2019), Springer, Cham, p. 251 (Paper 32)
Diestel, R.: Graph Theory, 2nd ed. Springer (2017)
Dong, F. M., Koh, K. M., Teo, K. L.: Chromatic Polynomials and Chromaticity of Graphs. World Scientific Publishing Company (2005)
Duncan, B.: Bell and Stirling numbers for disjoint unions of graphs. Congressus Numerantium 206 (2010)
Duncan, B., Peele, R. B.: Bell and Stirling numbers for graphs. J. Integer Seq. 12, Article 09.7.1 (2009)
Galvin, D., Thanh, D.T.: Stirling numbers of forests and cycles. Electron. J. Comb. 20, Paper P73 (2013)
Hertz, A., Hertz, A., Mélot, H.: Using graph theory to derive inequalities for the Bell numbers. J. Integer Seq. 24, Article 21.10.6 (2021)
Hertz, A., Mélot, H.: Counting the number of non-equivalent vertex colorings of a graph. Discrete Appl. Math. 203, 62–71 (2016) DOI: 10.1016/j.dam.2015.09.015
Hertz, A., Mélot, H., Bonte, S., Devillez, G.: Lower bounds and properties for the average number of colors in the non-equivalent colorings of a graph. Discrete Appl. Math. (2022). 10.1016/j.dam.2022.08.011 DOI: 10.1016/j.dam.2022.08.011
Kereskényi-Balogh, Z., Nyul, G.: Stirling numbers of the second kind and Bell numbers for graphs. Australas. J. Comb. 58, 264–274 (2014)
Odlyzko, A., Richmond, L.: On the number of distinct block sizes in partitions of a set. J. Comb. Theory Ser. A. 38(2), 170–181 (1985) DOI: 10.1016/0097-3165(85)90066-4
Sloane, N.: The on-line encyclopedia of integer sequences. http://oeis.org