Résumé : 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.

Résumé : 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.

Résumé : 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.

Résumé : 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.

Résumé : 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.

Résumé : 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.