Imprimer

journee.html

Programme de la 29ème journée JFRO

LE MARDI 4 JUIN 2013

Sur le thème

Structures et Algorithmique dans les Graphes

A L’Université Paris Diderot
Laboratoire d’Informatique Algorithmique : Fondements et Applications (LIAFA)
Amphithéâtre Alan Turing (Bâtiment Sophie Germain)

Plan d’accès

Inscription : merci de remplir le formulaire d’inscription

 10h00-10h25 Accueil des participants 10h25-10h30 Ouverture de la journée Michel Habib LIAFA, Univ. Paris Diderot & CNRS, France 10h30-11h15 3-coloring graphs with no induced 6-edge paths Maria Chudnovsky Department of Industrial Engineering and Operations ResearchDepartment of Mathematics Columbia University, USA Since graph coloring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Due to results of Kaminski and Lozin, and Hoyler, the problem remains NP-complete, unless H is the disjoint union of paths. Recently the question of coloring graphs with a fixed-length induced path forbidden has received considerable attention, and only a few cases of that problem remain open for k-coloring when k≥4. However, little is known for 3-coloring. Recently we have settled the first open case for 3-coloring; namely we showed that 3-coloring graphs with no induced 6-edge paths can be done in polynomial time. In this talk we will discuss some of the ideas of the algorithm. (This is joint work with Peter Maceli and Mingxian Zhong.) 11h15-12h Homomorphism and minor of signed bipartite graphs Reza Naserasr LRI, Univ. Paris-Sud & CNRS, France A signature on a graph is an assignment of signs (+ or -) to its edges. Resigning at a vertex x is changing the signs of all the edges incident to x. Let Σ be the set of negative edges. Two signatures Σ1 and Σ2 on a same graph are said to be equivalent if one can be obtained from the other by a sequence of resigning. A signed graph, denoted by (G, Σ), is a graph together with a set of equivalent signatures. A signed minor of (G, Σ) is a signed graph obtained from (G, Σ) by a sequence of (i) deleting edges or vertices, (ii) contracting positive edges, and (iii) resigning. A homomorphism of (G, Σ) to (H, Σ1) is a homomorphism of G to H which preserves signs of edges with respect to some signatures Σ’ and Σ1’ equivalent to Σ and Σ1 respectively. In this talk, we show that homomorphism of signed bipartite graphs captures the notion of graph homomorphisms. Thus, many coloring theories on graphs can be extended to this set of signed graphs. In particular we consider possible extensions of Hadwiger’s conjecture. We also show some relation to a conjecture of P. Seymour on edge-coloring of planar graphs. 12h00-14h00 Pause déjeuner 14h-14h45 Minimal bricks Maya Stein Centre for Mathematical Modeling (CMM) Universidad de Chile, Santiago, Chile A brick is a 3-connected bicritical graph. Bricks, together with braces, arise as building blocks in matching covered graphs. Norine and Thomas conjectured that (edge)-minimal bricks contain a (fixed) positive fraction of vertices of degree 3. The talk is on recent progress on this conjecture. 14h45-15h30 On the number of non-equivalent vertex colorings of a graph Alain Hertz École Polytechnique de Montréal et laboratoire GERAD Montréal, Canada We study the number of non-equivalent vertex colorings of a graph. We show the main similarities and differences between this new graph invariant and the well-known chromatic polynomial. Relations with the Stirling numbers of the second kind and with the Bell numbers are also given. Moreover, we characterize those graphs that minimize this new invariant when the maximum degree is fixed. (Joint work with Hadrien Mélot.) 15h30-16h00 Pause café 16h00-16h45 Minimum clique cover in claw-free perfect graphs and the weak Edmonds-Johnson property Flavia Bonomo Departamento de ComputaciónFacultad de Ciencias Exactas y Naturales Universidad de Buenos Aires, Argentina We give new algorithms for the minimum (weighted) clique cover in a claw-free perfect graph G, improving the complexity from O(|V(G)|5) to O(|V(G)|3). The new algorithms build upon neat reformulations of the problem: it basically reduces either to solving a 2-SAT instance (in the unweighted case) or to testing if a polyhedra associated with the edge-vertex incidence matrix of a bidirected graph has an integer solution (in the weighted case). The latter question was elegantly answered using neat polyhedral arguments by Schrijver in 1994. We give an alternative approach to this question combining pure combinatorial arguments (using techniques from 2-SAT and shortest paths) with polyhedral ones. Our approach is inspired by an algorithm from the Constraint Logic Programming community and we give as a side benefit a formal proof that the corresponding algorithm is correct (apparently answering an open question in this community). Interestingly, the systems we study have properties closely connected with the so-called Edmonds-Johnson property and we study some interesting related questions. Additionally, exploiting the properties of such systems in the unweighted case, we devise a simple (self-contained) augmenting path algorithm to compute concurrently a maximum cardinality stable set and a minimum (integer) clique cover. (Joint work with Gianpaolo Oriolo, Claudia Snels and Gautier Stauffer; this paper was presented at IPCO 2013.) 16h45-17h30 Recent trends in intersection graphs Martin Golumbic The Caesarea Rothschild Institute University of Haifa, Israel After a brief introduction, with examples, on the topic of intersection graphs and containment graphs, we will report on recent work on the intersection graphs of k-bend paths on a grid, the so-called Bk-VPG graphs.