Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GALaC
2-distance coloring of not-so-sparse graphs.
Clement Charpentier

16 May 2014, 14h30 - 16 May 2014, 15h30
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche :

Résumé :
The 2-distance coloring of a graph G is a proper coloring of G where every pair of vertices sharing a common neighbor
receives different colors.

The "maximum average degree" or "mad" of a graph is the maximum among the average degrees of its subgraphs.
This is a way to evaluate the density (or the sparseness) of a graph, both globally and locally.

Several results exist about the lesser number of colors needed for 2-distance coloring of graphs with bounded mad.
However, in all these results, the bound is strictly lesser than 4.

We present upper and lower bounds for the "2-distance chromatic number" of graphs with mad bounded by 2k for every k.

Pour en savoir plus :
Séminaires
Knowledge Graph Refinement based on Triplet BERT-N
Gestion de données du Web
Monday 29 November 2021 - 13h00
Salle : 455 - PCRI-N
Armita Khajeh Nassiri .............................................

A Hyper-graph Approach for Computing EL+-Ontology
Raisonnement automatique
Monday 15 November 2021 - 13h00
Salle : 445 - PCRI-N
Hui Yang .............................................

Semantic approaches to predict the presence of asb
Intégration de données et de connaissances
Monday 08 November 2021 - 13h00
Salle : 455 - PCRI-N
Thamer Mecharnia .............................................

Pierre Andrieu - Agrégation de classements pour le
Thursday 21 October 2021 - 00h00
Salle : 435 - PCRI-N
.............................................

A counting argument for graph colouring
Théorie des graphes
Friday 08 October 2021 - 11h00
Salle : 445 - PCRI-N
Francois Pirot .............................................