Programme de la 29ème journée JFRO
LE MARDI 4 JUIN 2013
Sur le thème
10h0010h25  Accueil des participants 
10h2510h30 
Ouverture de la journée Michel Habib LIAFA, Univ. Paris Diderot & CNRS, France

10h3011h15 
3coloring graphs with no induced 6edge paths Maria Chudnovsky Department of Industrial Engineering and Operations Research Columbia University, USA
Since graph coloring is an NPcomplete 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 NPcomplete, unless H is the disjoint union of paths. Recently the question of coloring graphs with a fixedlength induced path forbidden has received considerable attention, and only a few cases of that problem remain open for kcoloring when k≥4. However, little is known for 3coloring. Recently we have settled the first open case for 3coloring; namely we showed that 3coloring graphs with no induced 6edge 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.) 
11h1512h 
Homomorphism and minor of signed bipartite graphs Reza Naserasr LRI, Univ. ParisSud & 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 edgecoloring of planar graphs. 
12h0014h00  Pause déjeuner 
14h14h45 
Minimal bricks Maya Stein Centre for Mathematical Modeling (CMM) Universidad de Chile, Santiago, Chile
A brick is a 3connected 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.

14h4515h30 
On the number of nonequivalent vertex colorings of a graph Alain Hertz École Polytechnique de Montréal et laboratoire GERAD Montréal, Canada
We study the number of nonequivalent vertex colorings of a graph. We show the main similarities and differences between this new graph invariant and the wellknown 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.)

15h3016h00  Pause café 
16h0016h45 
Minimum clique cover in clawfree perfect graphs and the weak EdmondsJohnson property Flavia Bonomo Departamento de Computación Universidad de Buenos Aires, Argentina We give new algorithms for the minimum (weighted) clique cover in a clawfree 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 2SAT instance (in the unweighted case) or to testing if a polyhedra associated with the edgevertex 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 2SAT 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 socalled EdmondsJohnson property and we study some interesting related questions. Additionally, exploiting the properties of such systems in the unweighted case, we devise a simple (selfcontained) 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.) 
16h4517h30 
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 kbend paths on a grid, the socalled B_{k}VPG graphs.
