Une version chromatique des identités de Gallai renforçant la borne Theta-Lovasz
Denis Cornaz, Université Dauphine
Les identités de Gallai, dans les graphes sans triangle, peuvent s'exprimer avec le nombre clique et le nombre chromatique en utilisant le graphe aux arêtes. Si on supprime les arêtes du graphe aux arêtes correspondant à des pairs d'arcs simpliciales pour une orientation acyclique, on étend l'expression chromatique des identités de Gallai à tous les graphes. Etant donné un paramètre pris en sandwich entre les nombres clique et chromatique, on peut le calculer dans notre sous-graphe partiel du graphe aux arêtes pour obtenir un autre paramètre avec cette propriété sandwich. Pour la fonction Theta-Lovasz, le nouveau paramètre est toujours plus proche du nombre chromatique. Pour le nombre chromatique fractionnaire, le nouveau paramètre est toujours plus proche du nombre clique.
Résultats obtenus avec Vincent Jost (LIX) et Philippe Meurdesoif (Université Bordeaux 1)