Vendredi 16 Avril à 14h - William Lochet
Exploiting Dense Structures in Parameterized Complexity.

Over the past few decades, the study of dense structures (mainly graphs) from the perspective of approximation algorithms has become a wide area of research. In particular, properties of random samples have been successfully deployed to design approximation schemes for a number of fundamental problems on dense structures. Recently, we initiated the study of this class of graphs from the perspective of parameterized complexity. In particular, we obtain linear vertex kernels for Edge-Disjoint Paths, Edge Odd Cycle Transversal, Minimum Bisection, d-Way Cut, Multiway Cut and Multicut on everywhere dense graphs. In fact, these kernels are obtained by designing a polynomial-time algorithm when the corresponding parameter is at most Ω(n). Additionally, we obtain a cubic kernel for Vertex-Disjoint Paths on everywhere dense graphs. In this talk, we will first see how the properties of random samples can be used to design a subexponential-time algorithm and a linear kernel for the Edge Odd Cycle Transversal problem. Then we will see, using a much more structural approach, how to obtain a linear kernel for the Edge-Disjoint Paths problem.

This is based on a joint work with Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi which appeared in STACS 2021 and the preprint can be found in

Vendredi 9 Avril à 14h - Sang-Il Oum
A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles.

A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least ℓ, cycles of length p modulo q, cycles intersecting a prescribed set of vertices at least t times, and cycles contained in given ℤ2-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties.

Joint work with J. Pascal Gollin, Kevin Hendrey, Ken-ichi Kawarabayashi, and O-joung Kwon.

Lundi 29 Mars, Mercredi 31 mars et Vendredi 2 avril - Journées CALAMAR
Width Parameter
Connexion :

We organize a virtual meeting on March 29, 31 and April 2 on the topic of "Width Parameters". There will be 9 accessible talks on this topic, in a friendly and relaxed atmosphere. The goal is that everyone (including the speakers!) can learn from the recent development in the area. The two first days will be dedicated to the classical notions of tree-width, and clique-width / rank-width, and they will be followed by a third day dedicated to the recent notion of twin-width.

Marthe Bonamy, Nicolas Bousquet, Louis Esperet, et Daniel Gonçalves


Vendredi 26 Mars à 14h - Nacim Oijid
Complete coloring of signed graphs

Graph coloring is one of the most famous problems in Graph Theory. It has been declined into many problems by adding constraints. One of them is the notion of achromatic number, which is defined as the largest number of colors we can use to color a graph in such a way that each pair of colors appears on at least one edge. This notion of achromatic number has already led to many results on undirected graphs.

During this talk, I will present results on the achromatic number of signed graphs, obtained in collaboration with Julien Bensmail, François Dross and Eric Sopena during a three-month internship. We will see how classical operations on a signed graph can modify the achromatic number and what the complexity of computing this parameter is.

Vendredi 19 Mars à 14h - Gunnar Brinkmann
A survey of isomorphism rejection in structure generation programs

If you want to exhaustively enumerate a certain class of graphs, you have to solve two problems:

a.) how to construct all elements in the class

b.) how to avoid isomorphic copies

The first problem is often the more interesting and more challenging one. Unfortunately the solutions are often very much focused on the specific problem.

For b.) there are some standard techniques that can be applied to obtain efficient algorithms and programs. The topic of this talk will be to show some of these techniques.

First some examples of applications of structure enumeration will be presented. After that some techniques -- to be exact: orderly generation, the canonical construction path method, and the homomorphism principle-- will be demonstrated at examples. The methods will be explained in an informal and -- hopefully -- easily understandable way, so that also students should be able to follow the talk.

Vendredi 12 Mars à 14h - Gwenaël Joret
Approximating pathwidth for graphs of small treewidth

In this talk I will describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of O(t\sqrt{\log t}). This is the first algorithm to achieve an f(t)-approximation for some function f.

Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th+2 has treewidth at least t or contains a subdivision of a complete binary tree of height h+1. The bound th+2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c=2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth \Omega(k^c) has treewidth at least k or contains a subdivision of a complete binary tree of height k.

Joint work with Carla Groenland, Wojciech Nadara, and Bartosz Walczak.

Vendredi 26 Février à 14h - Vida Dujmovic
Stack-Number is not bounded by Queue-Number

Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999) asked the following about the two graph parameters: 1) Is stack-number bounded by queue-number? 2) Is queue-number bounded by stack-number?

We answer the first question in the negative. More specifically, we describe an infinite family of graphs all having queue number at most 4 but having unbounded stack number. The proof of this result uses only basic combinatorics (the Pigeonhole Principle and the Erdös-Szekeres Theorem) and the well-known Hex Lemma.

This is joint work with David Eppstein, Robert Hickingbotham, Pat Morin and David R. Wood.

Vendredi 5 Mars à 14h - Piotr Micek
Dimension, height, and large standard examples in planar posets

This will be an introductory presentation to poset's dimension. Already Dilworth has proved that for a poset to have large dimension, the poset must be wide. It does not have to be tall though. Indeed, so-called standard examples have height 2 and unbounded dimension. A remarkable feature of planar posets is that if they have large dimension then they are also tall. In other words, we can bound dimension of planar posets from above by a function of the height. Starting from the basics, we will go through a complete proof that the dimension of posets with outerplanar cover graphs is at most 4. We will discuss how to bound the dimension of a poset in terms of the (3h)-th weak coloring number of its cover graph. This implies bounds for the planar case and far beyond. We will discuss the current state-of-art and point the key open problems in the area.

Vendredi 19 Février à 14h - Edouard Bonnet
Twin-width and ordered binary structures

The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of its vertex set V(G), and every part X of every partition P of the sequence has at most d other parts Y of P with both at least one edge and at least one non-edge between X and Y. Twin-width is closely tied to total orders on the vertices, and can be extended to general binary structures. We will thus consider the twin-width of ordered binary structures, or if you prefer, matrices on a finite alphabet. This turns out to be key in understanding combinatorial, algorithmic, and model-theoretic properties of (hereditary) classes of those objects. We will see several characterizations of bounded twin-width for these classes. The main consequences in the three domains read as follows. Enumerative combinatorics: All the classes of 0,1-matrices with superexponential growth have growth at least n!. Algorithms: First-order model checking of ordered binary structures is tractable exactly when the twin-width is bounded. Finite model theory: Monadically-dependent and dependent hereditary classes of ordered binary structures are the same. In addition we get a fixed-parameter algorithm approximating matrix twin-width within a function of the optimum, which is still missing for unordered graphs.

Joint work with Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé.

Vendredi 5 Février à 14h - Zdeněk Dvořák
Towards geometry of graphs with sublinear separators

Many geometrically (and topologically) defined graph classes have sublinear separators (i.e., all graphs from the class as well as all their subgraphs have balanced separators of sublinear size). It seems plausible that conversely, all graphs with sublinear separators migth have geometric representations. We discuss some results related to this idea.

Vendredi 29 Janvier à 14h - Marcin Pilipczuk
Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths

In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in Pt-free graphs, that is, graphs excluding a fixed path as an induced subgraph. Their algorithm runs in time n^(O(log^3 n)), where t is assumed to be a constant.

Inspired by their ideas, we present an arguably simpler algorithm with an improved running time bound of n^(O(log^2 n)). Our main insight is that a connected Pt-free graph always contains a vertex w whose neighborhood intersects, for a constant fraction of pairs u v of vertices, a constant fraction of induced u − v paths. Since a Pt-free graph contains O(n^(t−1)) induced paths in total, branching on such a vertex and recursing independently on the connected components leads to a quasi-polynomial running time bound.

We also show that the same approach can be used to obtain quasi-polynomial-time algorithms for related problems, including Maximum Weight Induced Matching and 3-Coloring.

Vendredi 22 Janvier à 14h - Marthe Bonamy
Towards polynomial Chi-boundedness of graphs with no long path

There are graphs of arbitrarily high chromatic number which contain no triangle and in fact no short cycle. However, in some graph classes with enough structure, we can show that the chromatic number of the graphs is bounded by some function of their largest clique -- in other words, that class is chi-bounded. One of the first such results was by Gyarfas in 1987: for any t, the class of Pt-free graphs is chi-bounded. The corresponding function is unfortunately exponential, and it remains a major open problem whether we can replace it with a polynomial. Here, we consider a relaxation of this problem, where we compare the chromatic number with the size of the largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every t there exists a constant c such that every Pt-free graph which does not contain Kp,p as a subgraph is p^c-colourable.

This is joint work with Nicolas Bousquet, Michal Pilipczuk, Pawel Rzazewski, Stéphan Thomassé and Bartosz Walczak.

Vendredi 15 Janvier à 15h - Paul Seymour
The Erdos-Hajnal conjecture is true for excluding a five-cycle

In an n-vertex graph, there must be a clique or stable set of size at least Clog n, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph, the largest clique or stable set is bigger.

Erdos and Hajnal conjectured in 1977 that for every graph H, there exists c>0 such that every H-free graph has a clique or stable set of size at least |G|^c (``H-free'' means not containing H as an induced subgraph, and |G| means the number of vertices of G). This is still open, even for some five-vertex graphs H; and the case that has attracted most attention is when H is a cycle of length five.

It is true in that case. I will give a sketch of the proof, which is via applying a lemma about bipartite graphs, a variant of a theorem of I. Tomon.

This lemma has several other application to the Erdos-Hajnal conjecture. For instance, it implies that for every cycle C and forest T, there exists c>0 such that every graph that is both C-free and T'-free (where T' is the complement of T) has a clique or stable set of size |G|^c. (Until now this was open when C has length five and T is a 5-vertex path.)

Joint work with Maria Chudnovsky, Alex Scott and Sophie Spirkl.

Vendredi 8 Janvier à 14h - Bernard Lidický
11/4-colorability of subcubic triangle-free graphs

We prove that every connected subcubic triangle-free graph except for two exceptional graphs on 14 vertices has fractional chromatic number at most 11/4.
This is a joint work with Zdenek Dvorak and Luke Postle.

Vendredi 18 décembre à 14h - Candidats CNRS

Vendredi 11 décembre à 14h - Dimitri Lajou
Cartesian product of signed graphs

In this talk we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some Cartesian products. One of our main results is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by Imrich and Peterin (2018).
We also study the chromatic number of a signed graph, that is the minimum order of a signed graph to which the input signed graph admits a homomorphism, of graphs with underlying graph of the form $P_n \ssquare P_m$, of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles.

Vendredi 4 décembre à 14h - Louis Esperet
Universal graphs

A graph G is universal for some class F if it contains all the graphs of F as induced subgraph. The objective is to minimize the number of vertices of G. In this talk I will explain how to construct universal graphs for any given hereditary class of dense graphs, with a nearly optimal number of vertices. I will also explain several applications of our result: how to obtain nearly optimal universal posets (posets that contain all n-element posets), and how to encode reachability in digraphs in a nearly optimal way.

This is joint work with Marthe Bonamy, Carla Groenland, and Alex Scott

Vendredi 27 novembre à 14h - Noga Alon
Unitary Signings and Induced subgraphs of Cayley graphs

Let G be a Cayley graph of the elementary abelian 2-group Z_2^n with respect to a set S of size d. In joint work with Kai Zheng we show that for any such G,S and d, the maximum degree of any induced subgraph of G on any set of more than half the vertices is at least \sqrt d. This is deduced from the recent beautiful result of Huang who proved the above for the n-hypercube Q^n, in which the set of generators S is the set of all vectors of Hamming weight 1, establishing the sensitivity conjecture of Nisan and Szegedy. Motivated by his method we define and study unitary signings of adjacency matrices of graphs, and compare them to the orthogonal signings of Huang. Subsequent work regarding more general Cayley graphs will be mentioned as well.

Vendredi 20 novembre à 14h - Bojan Mohar
On the genus of dense graphs

The motivation for this talk is to find efficient methods for approximating the genus of graphs. In the setup of graph limits, any large dense graph can be approximated by a quasirandom graph based on a small weighted graph. The normalized version of the genus is a continuous function in this setup. From this top-down view of the problem, we are able to fins an EPTAS (efficient polynomial-time approximation scheme). The speaker will first provide a rough introduction and then will try to explain how various proof ingredients come together. The main results are joint work with Yifan Jing.

Vendredi 13 novembre à 14h - Nicolas Trotignon
Why even-hole-free graphs ?

Several recent works concern the class of even-hole-free graphs (where an even-hole-free graph is a graph whose chordless cycles are all of odd length). The goal of this talk is to survey some of them and also to explain why studying this class is of interest. At the end of the talk, we will sketch the proof of a result obtained jointly with Chinh Hoang : for every fixed integer k, rings of length k have unbounded rankwidth (where a ring of length k is a graphs that consists into k cliques arranged cyclically, such that a vertex has neighbors only its own clique and in the two cliques next to it, and moreover for every two vertices u, v in the same clique, N[u] is a subset or a superset of N[v]).

Mardi 10 novembre à 14h - Jan Volec
The codegree threshold of K4-

The codegree threshold ex_2(n,F) of a 3-uniform hypergraph (3-graph for short) F is the minimum D such that every 3-graph on n vertices in which every pair of its vertices is contained in at least D+1 hyperedges contains a copy of $F$ as a subhypergraph. In this talk, we focus on the codegree threshold of K4-, i.e., the unique 3-graph on 4 vertices with 3 hyperedges.

Using flag algebra techniques, we prove that ex_2(n, K4-)=n/4+O(1). This settles in the affirmative a conjecture of Nagle from 1999. In addition, we show that every near-extremal 3-graph G can be related to a quasi-random tournament T on the same vertex set such that G is close, in the so-called edit distance, to the 3-graph C(T) whose hyperedges are the cyclically oriented triangles of T. We also determine the exact value of ex_2(n,K4-) for infinitely many values of n using a close relation of the K4- codegree threshold to the existence of skew Hadamard matrices. In fact, we show that determining the exact value of ex_2(n, K4-) for n=4k-1 is equivalent to Seberry's conjecture stating that there exists a skew Hadamard matrix for any n=4k.

This is a joint work with Victor Falgas-Ravry, Oleg Pighurko and Emil Vaughan

Vendredi 6 novembre à 14h - Boram Park
The strong cliques in graphs with forbidden cycles

Given a graph G, the strong clique number of G, denoted SC(G), is the maximum size of a set S of edges such that every pair of edges in S has distance at most 2 in the line graph of G. As a relaxation of the renowned Erdős-Nešetřil conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. In this talk, we show that a {C_5, C_2k}-free graph G with Delta(G)>= 1 satisfies SC(G) <= k Delta(G)-(k-1), when either k>= 4 or k\in {2,3} and G is also C_3-free. This improves some results of Cames van Batenburg, Kang, and Pirot (2019). It is joint work with Eun-Kyung Cho, Ilkyoo Choi, Ringi Kim.

Vendredi 23 octobre à 14h - Lionel Eyraud-Dubois
Scheduling Independent Tasks on GPUs with co-scheduling effects, or Partitioning Pseudo-forests into Caterpillars

While studying a scheduling problem on GPUs, we stumbled on a graph problem: how to partition a pseudo-forest into edge-disjoint caterpillars. With some help from very kind members of the Graphs & Optimisation group, we obtained an optimal polynomial-time algorithm for this problem. We present the connection between the scheduling and partitioning problems, how and why this optimal algorithm works, and discuss several other related problems.

Vendredi 9 octobre à 14h - Alexandre Blanché
Gallai's path decomposition conjecture for planar graphs
Connexion: et salle 178 (hybride)

In 1968, Gallai conjectured that the edges of any connected graph on n vertices can be partitioned into at most (n+1)/2 egde-disjoint paths. This conjecture is still open to this day, but was proved on some graph classes such as graphs with at most one vertex of even degree (Lovász, 1968), graphs with maximum degree at most 5 (Bonamy et al., 2016) or graphs with treewidth at most 3 (Botler et al., 2017). We proved the conjecture on the class of planar graphs, i.e. graphs that can be drawn in the plane with no edges crossing. More precisely, we proved a stronger result: any connected planar graph on n vertices can be decomposed into at most n/2 paths, except K3 and K5 minus one edge.

(Based on joint works with Marthe Bonamy and Nicolas Bonichon)

Vendredi 2 octobre à 14h - Nicolas Bousquet
Independent Set Reconfiguration via Token Sliding

An independent set of a graph G is a subset of pairwise non incident vertices of G. Finding a maximum independent set in G is a problem that received a considerable attention in the last decades. In this talk, we will look at this problem via the lens of reconfiguration. Two independent sets X,Y are said to be adjacent (in the Token Sliding (TS) model) if there exist two vertices x,y such that X-x= Y-y. A TS-sequence of independent sets is a sequence of independent sets such that any pair of consecutive independent sets in the sequence are TS-adjacent.

In 2005, Hearn and Demaine showed that it is PSPACE-complete to determine, given two k-independent sets X,Y of G if there exists a TS-sequence between X and Y. This result had important consequences and opened a new direction of research. Since then, numerous results have been obtained. We will overview some of the most relevant results in this field and mention some possible future research directions.

(Based on joint works with Valent Bartier, Marthe Bonamy, Clément Dallard, Kyle Lomer, Amer Mouawad, Moritz Mühlenthaler)

Vendredi 25 septembre à 14h - Jonathan Narboni
On Vizing's edge coloring question

In his 1965 seminal paper on edge coloring, Vizing proved that a (Delta+1)-edge coloring can be reached from any given proper edge coloring through a series of Kempe changes, where Delta is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge coloring be reached from any given proper edge coloring through a series of Kempe changes? In other words, if the graph is Delta-edge-colorable, can we always reach a Delta-edge-coloring? We discuss a key ingredient in Vizing's original paper, namely the use of fans; we show how to extend the notion and answer his question in the affirmative for all triangle-free graphs.

Vendredi 18 septembre à 14h - Rose McCarty
Colouring visibility graphs

We discuss recent chi-boundedness results on visibility graphs. The visibility graph of a finite set of points S on a Jordan curve J has vertex set S, and two points in S are adjacent if the (open) segment between them is contained in the interior of J. We prove that such a graph with clique number w has chromatic number at most 3*4^{w-1}, and that w can be computed in polynomial time. Moreover, these results hold in the pseudo-visibility setting. While we focus on colouring, the talk will also serve as an introduction to visibility graphs.

This is joint work with James Davies, Tomasz Krawczyk, and Bartosz Walczak.

Vendredi 11 septembre à 14h - Irena Penev
Coloring certain even-hole-free graphs

Abstract here

Emplois - Stages


GT Graphes et Optimisation


edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki