Présentation
Environ un vendredi par mois, l'équipe GOAL du LIRIS organise un séminaire autour des graphes et de ses applications. Ce séminaire est ouvert à tous.
Prochains séminaires
Vendredi 3 juillet 2015 à 10h00 (Nautibus, salle C5)
-
Aurélie Lagoutte , LIP - ENS Lyon
Coloring graphs with no even hole of length at least 6: the triangle-free case.
We prove that the class of graphs with no triangle and no induced cycle of even length at least 6 has bounded chromatic number. It is well-known that even-hole-free graphs are $\chi$-bounded but we allow here the existence of C_4. The proof relies on the concept of Parity Changing Path, an adaptation of Trinity Changing Path which was recently introduced by Bonamy, Charbit and Thomassé to prove that graphs with no induced cycle of length divisible by three have bounded chromatic number.
Séminaires passés
Vendredi 7 novembre 2014 à 13h30 (Nautibus, salle C4)
-
Arnaud Mary , LBBE, Université de Lyon 1
Partitions amicales dans les graphes réguliers
Une partition amicale (friendly partition) d'un graphe est une bipartition de ses sommets pour laquelle chaque sommet a au moins autant de voisins dans sa partie que dans l'autre. Nous nous intéresserons aux partitions amicales des graphes réguliers. Dans un graphe d-régulier les deux parties d'une partition amicale induisent deux graphes de degré minimum d/2. Tout graphe régulier n'admet pas forcément de partition amicale en revanche il est conjecturé que tout graphe suffisamment grand admet une partition amicale.
Vendredi 12 décembre 2014 à 10h00 (Nautibus, salle C5)
-
Julien Bensmail, LIP, ENS de Lyon
Strong edge-coloring of (3, Delta)-bipartite graphs
An edge-coloring of a graph G is strong if its every color class is an induced matching. The strong chromatic index of G, denoted chi's(G), is the least number of colors in a strong edge-coloring of G. Greedy coloring arguments show that chi's is upper-bounded by roughly 2Delta^2, where Delta denotes the maximum degree of any graph, though this upper bound is not reached in general. A long-standing conjecture of Erdos and Nesetril (1989) states that the right upper bound on the strong chromatic index should actually be roughly 1.25Delta^2, which would be tight as confirmed by a particular family of graphs with a lot of small cycles (C4's and C5's). Excluding small cycles (i.e. with length at most 5) in a graph is expected to make its strong chromatic index decrease, as confirmed notably by Mahdian (2000) for C4-free graphs. This observation made Faudree, Gyarfas, Schelp and Tuza (1990) conjecture that the strong chromatic index of bipartite graphs (which have no C3's and C5's) should be upper-bounded by Delta^2. In the continuity of previous results of Steger and Yu (1993) and Nakprasit (2008), we verify this conjecture for bipartite graphs whose one part is of maximum degree at most 3.
This is a joint work with A. Lagoutte and P. Valicov.
Vendredi 13 février 2015 à 10h (Nautibus, salle C5)
-
Gabriel Renault, Université de Mons
A propos des jeux dead-ending en version misère
Les jeux combinatoires sont des jeux finis à information complète, deux joueurs et sans hasard. En convention normale, un joueur perd lorsqu'il ne peut plus jouer, alors que ce même joueur gagne en convention misère. La théorie des jeux combinatoires développée par Berlekamp, Conway et Guy pour les jeux en convention normale ne fonctionne pas aussi bien en version misère, c'est pourquoi nous nous intéressons ici à un sous-ensemble de jeux, appelés dead-ending, pour lesquels on s'assure que lorsqu'un joueur ne peut plus jouer à partir d'une position, il ne pourra plus jamais jouer dans cette partie quelle que soit la séquence de coups de son adversaire. Les jeux combinatoires peuvent être représentés par des arbres dans lesquels les fils d'un nœud représentent les positions atteignables par les joueurs depuis la position représentée par le nœud en question. Nous étudions les propriétés de la décomposition des jeux dead-ending en somme de jeux et les utilisons pour simplifier ces arbres, donnant une forme canonique unique à ces jeux, et nous assurons que l'inverse de tout jeu inversible est naturel.
Vendredi 6 mars 2015 à 10h30 (Nautibus)
-
Florent Foucaud , LIMOS, Université de Clermont-Ferrand II
Homomorphism bounds for K4-minor-free graphs
A homomorphism of graph G to graph H is a function h from V(G) to V(H) which preserves the edges, i.e. if u,v are adjacent in G, then h(u),h(v) are adjacent in H. Homomorphisms extend the classic notion of proper graph colourings. Given a graph class C, an interesting optimization question is whether there is a graph to which all members of C admit a homomorphism (this graph is called a bound for C). If there exists one, what is the smallest order of such a bound? For example, all planar graphs admit a homomorphism to the graph K4 (this is the Four Colour Theorem), but no smaller graph is a bound. In this talk, we discuss the related problem of determining bounds for planar graphs and their subclasses, with some additional girth restrictions. Our focus will be on K4-minor-free graphs, i.e. series-parallel graphs.
This is joint work with Laurent Beaudou and Reza Naserasr.
Mardi 14 avril 2015 à 14h00 (Nautibus, salle C5)
-
Michel Habib , LIAFA - CNRS, Université Paris Diderot, Projet INRIA GANG
Graph seaches and community detection
I will present some new theoretical aspects of graph searches and then how to use this new framework to design new heuristics for community detection in huge graphs. To conclude, I will present a nice graph problem arising from biology (analysis of reads networks as can be done in metagenomics). In this application the aim is to find efficient algorithmic tools to classify a huge number of graphs with respect to there biological properties