Groupe d’études et de recherche en analyse des décisions

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

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 \(\mathcal{B}(G)\) est le nombre de colorations non équivalentes des sommets de \(G\). Nous déterminons une borne inférieure serrée pour \(\mathcal{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.

, 14 pages