A sharp lower bound on the number of ...
Document type :
Compte-rendu et recension critique d'ouvrage
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]
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
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 >
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 :
Source :
Files
- https://hal.inria.fr/hal-01944274/document
- Open access
- Access the document
- https://hal.inria.fr/hal-01944274/document
- Open access
- Access the document
- https://hal.inria.fr/hal-01944274/document
- Open access
- Access the document
- document
- Open access
- Access the document
- numcolSoumissionRevision.pdf
- Open access
- Access the document