*   Domaine de compétence Optimisation Combinatoire   *
  *    Séminaire
  o    2018 - 2019
  o    2017 - 2018
  o    2016 - 2017
  o    2015 - 2016
  o    2014 - 2015
  o    2013 - 2014
  o    2012 - 2013
  o    2011 - 2012
  o    2010 - 2011
  o    2009 - 2010
  o    2008 - 2009
  o    2007 - 2008
  o    2006 - 2007
  o    2005 - 2006
  o    2004 - 2005
  o    2003 - 2004
  *    Evénements
  *    Liens

Séminaires 2018 - 2019

Ceci est la page web du séminaire de l'équipe Optimisation Combinatoire du laboratoire G-SCOP, à Grenoble.

Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à 14h30 en Salle C319. Les responsables sont Louis Esperet et András Sebő, n'hésitez pas à les contacter.

22 novembre 2018 Jean-Florent Raymond
(TU Berlin)
On the density of critical graphs without large cliques
9 octobre 2018 Tom kelly
(Université de Waterloo)
On the density of critical graphs without large cliques
  • Jeudi 22 novembre 2018 (à 14h30): Jean-Florent Raymond (TU Berlin) : Énumérer les dominants dans les graphes sans triangle

    Étant donné un graphe, peut-on efficacement lister tous ses ensembles dominants minimaux ? Comme ceux-ci peuvent être en nombre exponentiel (en la taille du graphe), on cherche ici un algorithme dont le temps d'exécution est borné polynomialement en fonction de la taille du résultat (en non en fonction de la taille de l'entrée comme habituellement). L'existence d'un algorithme efficace pour énumérer les dominants minimaux est un problème ouvert depuis plusieurs décennies et a des liens avec de nombreux autres problèmes d'autres domaines. Dans cet exposé, je présenterai un algorithme efficace dans les graphes sans triangle, ce qui répond à une question de Kanté et al.

    Travail commun avec Marthe Bonamy, Oscar Defrain et Marc Heinrich.
    lien vers l'article


  • Mardi 9 octobre 2018 (à 11h): Tom Kelly (Université de Waterloo) : On the density of critical graphs without large cliques

    A graph is k-critical if it has chromatic number k and every proper subgraph is (k - 1)-colorable. The density of critical graphs has been extensively studied. We present an improvement on the best known lower bound for the density of critical graphs without large cliques. We also discuss a connection to list-coloring and generalizations of Reed's Conjecture.

    Joint work with Luke Postle.