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

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

Hertz Alain, Mélot Hadrien , "Counting the number of non-equivalent vertex colorings of a graph" in Discrete Applied Mathematics, 203, 62-71

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

Abstract(s) :

(Anglais) We study the number P(G) of non-equivalent ways of coloring a given graph G, also known as the (graphical) Bell number of G. We show some similarities and differences between this graph invariant and the well known chromatic polynomial. We then relate P(G) to Stirling numbers of the second kind, and to Bell, Fibonacci, and Lucas numbers, by computing the values of this invariant for some families of graphs. We finally study upper and lower bounds on P(G) for graphs with fixed maximum degree.

Mots-clés :
  • (Anglais) chromatic polynomial
  • (Anglais) non-equivalent colorings
  • (Anglais) graphical Bell numbers