Homepage
Previous JFRO
Organizing committee
Contact
29th Ile-de-France Operation Research Day
Structures et Algorithmique dans les Graphes
Date
This day took place
Tuesday, the 04 June 2013
Place
A L’Université Paris Diderot Laboratoire d’Informatique Algorithmique : Fondements et Applications (LIAFA) Amphithéâtre Alan Turing (Bâtiment Sophie Germain)

Program of the day


10h00-10h25
Accueil

10h25-10h30
Ouverture de la journée
Michel Habib (LIAFA, Univ. Paris Diderot & CNRS)

10h30-11h15
3-coloring graphs with no induced 6-edge paths
Maria Chudnovsky (Department of Industrial Engineering and Operations Research Department of Mathematics Columbia University, USA), Peter Maceli and Mingxian Zhong
Abstract : 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.

11h15-12h00
Homomorphism and minor of signed bipartite graphs
Reza Naserasr (LRI, Univ. Paris-Sud & CNRS)
Abstract : 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 Sigma be the set of negative edges. Two signatures Sigma1 and Sigma2 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, Sigma), is a graph together with a set of equivalent signatures. A signed minor of (G, Sigma) is a signed graph obtained from (G, Sigma) by a sequence of (i) deleting edges or vertices, (ii) contracting positive edges, and (iii) resigning. A homomorphism of (G, Sigma) to (H, Sigma1) is a homomorphism of G to H which preserves signs of edges with respect to some signatures Sigma’ and Sigma1’ equivalent to Sigma and Sigma1 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

14h00-14h45
Minimal bricks
Maya Stein (Centre for Mathematical Modeling (CMM), Universidad de Chile, Santiago, Chile)
Abstract : 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) and Hadrien Mélot
Abstract : 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.

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ón Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina), Gianpaolo Oriolo , Claudia Snels and Gautier Stauffer
Abstract : 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.

16h45-17h30
Recent trends in intersection graphs
Martin Golumbic (The Caesarea Rothschild Institute, University of Haifa, Israel)
Abstract : 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.

Choose language : Français English