G-2015-04
A sharp lower bound on the number of non-equivalent colorings of graphs of order n and maximum degree n−3
, , et référence BibTeX
Deux colorations des sommets d'un graphe sont dites équivalentes si elles correspondent à la même partition de l'ensemble des sommets en classes de couleurs. Le nombre de Bell graphique B(G)
est le nombre de colorations non équivalentes des sommets de G
. Nous déterminons une borne inférieure serrée pour B(G)
lorsque G
est d'ordre n
et a un degré maximum n−3
. De plus, nous caractérisons les graphes pour lesquels cette borne est atteinte.
Paru en janvier 2015 , 14 pages
Axe de recherche
Publication
jan. 2018
, , et
Discrete Applied Mathematics, 234, 3–11, 2018
référence BibTeX