[en] 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.
Research center :
CREMMI - Modélisation mathématique et informatique
Disciplines :
Mathematics
Author, co-author :
Absil, Romain ; Université de Mons > Faculté des Sciences > Algorithmique
Camby, Eglantine
Hertz, Alain
Mélot, Hadrien ; Université de Mons > Faculté des Sciences > Algorithmique
Language :
English
Title :
A sharp lower bound on the number of non-equivalent colorings of graphs of order n and maximum degree n-3
Publication date :
10 January 2018
Journal title :
Discrete Applied Mathematics
ISSN :
0166-218X
eISSN :
1872-6771
Publisher :
Elsevier, Amsterdam, Netherlands
Volume :
234
Pages :
3-11
Peer reviewed :
Peer Reviewed verified by ORBi
Research unit :
S825 - Algorithmique
Research institute :
R300 - Institut de Recherche en Technologies de l'Information et Sciences de l'Informatique R150 - Institut de Recherche sur les Systèmes Complexes
