[en] Average number of colors; [en] Graphical Bell numbers; [en] Graph coloring
Abstract :
[en] A coloring of a graph is an assignment of colors to its vertices such that adjacent vertices have different colors. Two colorings are equivalent if they induce the same partition of the vertex set into color classes. Let $avcol(G)$ be the average number of colors in the non-equivalent colorings of a graph $G$. We give properties and state open problems of this recently defined graph invariant.
Research center :
CREMMI - Modélisation mathématique et informatique
Disciplines :
Electrical & electronics engineering Mathematics
Author, co-author :
Devillez, Gauvain ; Université de Mons > Faculté des Sciences > Service d'Informatique théorique
Hertz, Alain
Mélot, Hadrien ; Université de Mons > Faculté des Sciences > Service Algorithmique
Bonte, Sébastien ; Université de Mons > Faculté des Sciences > Service des Systèmes d'information
Hauweele, Pierre ; Université de Mons > Faculté des Sciences > Service Algorithmique
Language :
English
Title :
On the average number of colors in the non-equivalent colorings of a graph
Publication date :
11 June 2021
Number of pages :
23
Event name :
34th Conference of the European Chapter on Combinatorial Optimization (ECCO 2021)
Event place :
Madrid, Spain
Event date :
2021
Research unit :
S825 - Algorithmique
Research institute :
R300 - Institut de Recherche en Technologies de l'Information et Sciences de l'Informatique R150 - Institut de Recherche sur les Systèmes Complexes
