Site

Exposés

Les GT se tiennent un jeudi sur deux de 14h à 15h (salle variables pour commencer).

Prochains exposés :

Jeudi 28 mars 2013 - Nicolas Bousquet (LIRMM) - Transversaux et VC-dimension - Résultats combinatoires et applications.
14 h 00 - Salle A102
Résumé : Etant donné un graphe, la notion de vertex cover (ensemble de sommet qui intersecte toute les arêtes) est liée à celle de matching (ensemble d’arêtes disjointes). Par exemple, la taille d’un vertex cover est au moins celle d’un matching. Réciproquement, la taille minimale d’un vertex cover est au plus deux fois celle d’un matching maximal. Les notions de vertex covers et matchings se généralisent en transversaux et packings dans les hypergraphes. Malheureusement, la taille d’un transversal n’est plus bornée par celle du packing.

Nous introduirons alors la notion de VC-dimension qui permet de borner le transversal en fonction de sa relaxation fractionnaire. Nous verrons ensuite que ce résultat peut se généraliser, sous certaines conditions, pour lier les tailles de transversaux et de packings. Tout au long de l’exposé, les résultats seront illustrés par des applications en théorie des graphes.


Jeudi 14 février 2013 - Zhzntao Li (LIP-MC2-ENS Lyon) - A characterization of restricted box graphs.
14 h 00 - Salle A002
Résumé : We consider a conjecture of Scott on $\chi$-bounded classes of graphs. A hereditary class (a class closed under induced subgraphs) is $\chi$-bounded if the chromatic number of every graph in the class is bounded by a function (depending only on the class) of the size of the largest clique.

Scott conjectured that for any graph $H$, the class of graphs excluding $H$ and all subdivisions of $H$ as an induced subgraph is $\chi$-bounded. Scott proved his conjecture when $H$ is a tree but Pawlik et al. recently showed it is false when $H$ is a specific subdivision of $K_5$. We study their counter-example and show that Scott’s conjecture is in fact false when $H$ is a 2-subdivision of $K_4$ (the graph obtained from $K_4$ by subdividing each edge twice). We do so by characterizing all 2-subdivisions that do not appear in their counter-example and thus show Scott’s conjecture is false for many other graphs. As an intermediate result, we characterize all 2-subdivision which are ``restricted box graphs’’, the intersection graph of two dimensional axis-parallel boxes with some restrictions on the placement of these boxes. This is joint work with Jérémie Chalopin, Louis Esperet, Frantisek Kardos, Patrice Ossona de Mendez and Stéphan Thomassé.

Exposés

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki