Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire du LRI
Une preuve courte d'un résultat de choisissabilité dans les graphes planaires
Nathann Cohen

03 February 2012, 14:30 - 03 February 2012, 15:30
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche :

Résumé :
L'index chromatique d'un graphe -- noté chi'(G) -- est égal au nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de telle facon que deux arêtes incidentes aient des couleurs différentes (on dit alors que la coloration est propre).
L'arête-choisissabilité est une forme contrainte de coloration d'arêtes : on commence par associer a chaque arête du graphe une liste de k entiers arbitraires, puis on tente de colorer proprement les arêtes en n'utilisant pour celles-ci que les couleurs disponibles dans leurs istes associées. Le plus petit $k$ tel qu'il existe pour toute assignation de liste une telle coloration propre est noté chi'_c(G). La list-coloring conjecture suppose depuis longtemps l'égalité chi'(G) = chi'_c(G) mais nous en sommes encore loin. Cet exposé consiste en une preuve courte d'un résultat de Borodin qui affirme que les graphes planaires de degré maximum Delta geq 9 vérifient chi'_c(G) leq Delta+1. La coloration s'obtient à l'aide d'un algorithme simple consistant en deux opérations et découle de la preuve du résultat.

Pour en savoir plus :
Séminaires
Refining Transitive and Pseudo-Transitive Relation
Web data management
Monday 24 January 2022 - 13:00
Salle : 455 - PCRI-N
Shuai Wang .............................................

Discovering Causal Rules in Knowledge Graphs using
Integration of Data and Knowledge
Monday 10 January 2022 - 15:00
Salle : 455 - PCRI-N
Lucas Simonne .............................................

Meta-Learning for Few-Shot Link Prediction in Know
Integration of Data and Knowledge
Monday 13 December 2021 - 13:00
Salle : 455 - PCRI-N
Taha Halal .............................................

Knowledge Graph Refinement based on Triplet BERT-N
Web data management
Monday 29 November 2021 - 13:00
Salle : 455 - PCRI-N
Armita Khajeh Nassiri .............................................

A Hyper-graph Approach for Computing EL+-Ontology
Automated Reasoning
Monday 15 November 2021 - 13:00
Salle : 445 - PCRI-N
Hui Yang .............................................