Title :

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

Author(s) :

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

Journal title :

Discrete Applied Mathematics

Pages :

3-11

Publisher :

Elsevier

Publication date :

2018-01

ISSN :

0166-218X

English keyword(s) :

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

HAL domain(s) :

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

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Popular science :

Non

Collections :

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

Source :

Harvested from HAL