Retour

G-2015-04

A sharp lower bound on the number of non-equivalent colorings of graphs of order n and maximum degree n3

, , 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 n3. De plus, nous caractérisons les graphes pour lesquels cette borne est atteinte.

, 14 pages

Axe de recherche

Publication

, , et
Discrete Applied Mathematics, 234, 3–11, 2018 référence BibTeX