DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
Rechercher
(titres de publication, de périodique et noms de colloque inclus)
2018-01-10 - Article/Dans un journal avec peer-review - Anglais - 9 page(s)

Absil Romain , Camby Eglantine, Hertz Alain, Mélot Hadrien , "A sharp lower bound on the number of non-equivalent colorings of graphs of order n and maximum degree n-3" in Discrete Applied Mathematics, 234, 3-11

  • Edition : Elsevier Science, Amsterdam (The Netherlands)
  • Codes CREF : Théorie des graphes (DI1146)
  • Unités de recherche UMONS : Algorithmique (S825)
  • Instituts UMONS : Institut de Recherche en Technologies de l’Information et Sciences de l’Informatique (InforTech), Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Modélisation mathématique et informatique (CREMMI)
Texte intégral :

Abstract(s) :

(Anglais) 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.