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
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - 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 metadatas

https://hal.inria.fr/hal-01944274
Contributor : Bernard Fortz <>
Submitted on : Tuesday, December 4, 2018 - 3:09:40 PM
Last modification on : Tuesday, September 17, 2019 - 4:20:06 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, Elsevier, 2018, 234, pp.3-11. ⟨hal-01944274⟩

Share

Metrics

Record views

56

Files downloads

185