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 \(\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.
Paru en janvier 2015 , 14 pages
Axe de recherche
Publication
jan. 2018
, , et
Discrete Applied Mathematics, 234, 3–11, 2018
référence BibTeX