Titre :

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

Auteur(s) :

Absil, Romain [Auteur]
Institute of Computer Science [Mons]
Camby, Eglantine [Auteur]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]
Integrated Optimization with Complex Structure [INOCS]
Hertz, Alain [Auteur]
Groupe d’études et de recherche en analyse des décisions [GERAD]
Melot, Hadrien [Auteur]
Institute of Computer Science [Mons]

Titre de la revue :

Discrete Applied Mathematics

Pagination :

3-11

Éditeur :

Elsevier

Date de publication :

2018-01

ISSN :

0166-218X

Mot(s)-clé(s) en anglais :

Non-equivalent colorings
Graphical Bell number
Extremal theory
Fixed maximum degree

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

Two vertex colorings of a graph G are equivalent if they induce the same partition of thevertex set into color classes. The graphical Bell number B(G) is the number of non-equivalentvertex colorings of G. We determine a ...
Lire la suite >Two vertex colorings of a graph G are equivalent if they induce the same partition of thevertex set into color classes. The graphical Bell number B(G) is the number of non-equivalentvertex colorings of G. We determine a sharp lower bound on B(G) for graphs G of order nand maximum degree n − 3, and we characterize the graphs for which the bound is attained.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL