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