Skip to Main content Skip to Navigation
New interface
Journal articles

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

Romain Absil 1 Eglantine Camby 2, 3 Alain Hertz 4 Hadrien Melot 1 
3 INOCS - Integrated Optimization with Complex Structure
Inria Lille - Nord Europe, ULB - Université libre de Bruxelles, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : Two vertex colorings of a graph G are equivalent if they induce the same partition of the vertex set into color classes. The graphical Bell number B(G) is the number of non-equivalent vertex colorings of G. We determine a sharp lower bound on B(G) for graphs G of order n and maximum degree n − 3, and we characterize the graphs for which the bound is attained.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-01944274
Contributor : Bernard Fortz Connect in order to contact the contributor
Submitted on : Tuesday, December 4, 2018 - 3:09:40 PM
Last modification on : Tuesday, December 6, 2022 - 12:42:13 PM

File

numcolSoumissionRevision.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01944274, version 1

Collections

Citation

Romain Absil, Eglantine Camby, Alain Hertz, Hadrien Melot. A sharp lower bound on the number of non-equivalent colorings of graphs of order n and maximum degree n − 3. Discrete Applied Mathematics, 2018, 234, pp.3-11. ⟨hal-01944274⟩

Share

Metrics

Record views

57

Files downloads

94