Vendredi 2 Juillet à 14h - Théo Pierron
Local certification of minor-free classes and MSO properties.
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Local certification consists in assigning labels to the nodes of a graph in order to certify that some given property is satisfied, in such a way that the labels can be checked locally. In this talk, our goal is to certify that a graph G belongs to a given graph class. Such certifications exist for trees, planar graphs and graphs embedded on surfaces with labels of logarithmic size. We present some generic tools which allow us to certify the H-minor-free graphs (with logarithmic labels) for each small enough H. More generally, we consider classes defined by any MSO formula (i.e. the MSO-model checking problem), and show a local version of the well-known Courcelle theorem: in bounded treedepth graphs, logarithmic certificates can be obtained for any MSO formula.
This is joint work with Nicolas Bousquet and Laurent Feuilloley.

Vendredi 25 Juin à 14h - Interns
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
Paul Bastide: Burning giant sequoias.
How fast can a rumor propagate in a graph? One measure of that, introduced by Bonato, Janssen and Roshanbin, is the burning number b(G) of a graph G. At step 1, we set a vertex on fire. At every step i > 1, all neighbours of a vertex on fire catch fire themselves, and we set a new vertex on fire. If at the end of step k the whole graph is on fire, then the graph is k-burnable. The burning number of G is defined to be the least k such that G is k-burnable. In this talk we present results on the burning number for p-caterpillars or trees that are distance p-dominated by a path.

Sasha Darmon: Coloration de graphes dégénéré.
Un graphe k-dégénéré est un graphe dont chacun de ses sous-graphes possède au moins un sommet de degré inférieur à k. En 1994 par l'étude des décompositions des graphes complets en union de graphes dégénérés, Michael Tarsi a proposé la conjecture suivante : " L'union d'un graphe graphe 1-dégénéré et d'un graphe 2-dégénéré est 5-colorable". Avec François Dross, nous avons formé diverses réductions de cette classe de graphes de façon à cerner (et idéalement réfuter) l'existence d'un contre-exemple à cette conjecture.

Clément Legrand-Duchesne: Kempe changes on ∆-colorings.
Any graph G can be colored greedily with ∆+1 colors, where ∆ is the maximum degree of G. Brooks' theorem states that all graphs but cliques and odd cycles can in fact be colored using at most ∆ colors. A Kempe change consist in swapping two colors in a maximal bichromatic component, thereby resulting in a different proper coloring of G. Mohar conjectured in 2005 that there exists a sequence of Kempe change between any two ∆-colorings of such graphs. This was proven true in all graphs but the 3-prism by Feghali et al. and Bonamy et al. . However the sequence they provided has exponential length. We prove that there exists one of length O(∆n²).

Pierre-Marie Marcille: Going wide with the 1-2-3 Conjecture.
In the so-called 1-2-3 Conjecture, the question is, for any connected graph not isomorphic to $K_2$, whether we can label its edges with 1, 2, 3 so that no two adjacent vertices are incident to the samesum of labels.
In this presentation, we introduce a new general problem, which holds essentially as a generalisation of the 1-2-3 Conjecture to a larger range. In this variant, a radius $r \geq 2$ is fixed, and the main task, given a graph, is, if possible, to label its edges so that any two vertices at distance at most $r$ are distinguished through their sums of labels assigned to their edges at distance at most $r$.

Vendredi 18 Juin à 14h - Amedeo Sgueglia
Factors in randomly perturbed graphs.
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We study the model of randomly perturbed dense graphs, which is the union of any n-vertex graph G_\alpha with minimum degree at least \alpha n and the binomial random graph G(n,p). In this talk, we shall examine the following central question in this area: to determine when G_\alpha \cup G(n,p) contains H-factors, i.e. spanning subgraphs consisting of vertex disjoint copies of the graph H. We offer several new sharp and stability results.

This is joint work with Julia Böttcher, Olaf Parczyk, and Jozef Skokan.

Vendredi 04 Juin à 14h - Aline Parreau
Locating-dominating sets in digraphs.
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

A dominating set of (di)graph is locating-dominating if every vertex not in has a unique set of (in-)neighbours within. Ore's theorem states that every (non oriented) graph of order n has a dominating set of size at most n/2. It is conjectured by Garijo, Gonzalez that this is strill true for locating-dominating sets if the (non oriented) graph has no twins.

We consider this question for oriented graphs and prove that it is still true for tournaments, acyclic graphs and local tournaments. Some twin-free digraphs need already 2n/3 vertices to be dominated. We prove in this direction that any twin-free oriented graph of order n has a LD-set of size 4n/5.

Joint work with Thomas Bellito, Caroline Brosse, Florent Foucaud, Shahrzad Heydarshahi et Benjamin Lévêque.

Vendredi 21 Mai à 14h - František Kardoš
Fractional vertex-arboricity of planar graphs.
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We initiate a systematic study of the fractional vertex-arboricity of planar graphs and demonstrate connections to open problems concerning both fractional coloring and the size of the largest induced forest in planar graphs. In particular, the following three long-standing conjectures concern the size of a largest induced forest in a planar graph, and we conjecture that each of these can be generalized to the setting of fractional vertex-arboricity. In 1979, Albertson and Berman conjectured that every planar graph has an induced forest on at least half of its vertices, in 1987, Akiyama and Watanabe conjectured that every bipartite planar graph has an induced forest on at least five-eighths of its vertices, and in 2010, Kowalik, Lužar, and Škrekovski conjectured that every planar graph of girth at least five has an induced forest on at least seven-tenths of its vertices. We make progress toward the fractional generalization of the latter of these, by proving that every planar graph of girth at least five has fractional vertex-arboricity at most 2-1/324.

This is a joint work with Marthe Bonamy, Tom Kelly and Luke Postle.

Vendredi 14 Mai à 14h - Pegah Pournajafi
Burling Graphs Revisited.
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

The Burling graphs form a class of triangle-free graphs with unbounded chromatic number. This class has attracted some attention because of its geometric representation and its importance in studying questions about chromatic number in hereditary classes of graphs. In this talk, we introduce some equivalent definitions of Burling graphs and then explain how one of these definitions can help us to find information about the structure of the graphs in this class.

This talk is based on joint work with Nicolas Trotignon. Some results are from https://arxiv.org/abs/2104.07001.

Vendredi 7 Mai à 14h - Carl Feghali
Colorings and decompositions of planar graphs.
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

In this talk, I review some of the results and proof methods on colorings, list colorings and decompositions of planar graphs, triangle-free planar graphs and planar graphs of girth 5. I end the talk by discussing some recent partial progress, obtained in join work with Robert Šámal, on a possible strengthening suggested by Kawarabayashi and Thomassen, of the celebrated Grözsch's theorem that every triangle-free planar graph is 3-colorable.

Vendredi 30 Avril à 15h - Daniel Cranston
In Most 6-regular Toroidal Graphs All 5-colorings are Kempe Equivalent.
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

A Kempe swap in a proper coloring interchanges the colors on some maximal connected 2-colored subgraph. Two k-colorings are k-equivalent if we can transform one into the other using Kempe swaps. We show that if G is 6-regular with a toroidal embedding where every non-contractible cycle has length at least 7, then all 5-colorings of G are 5-equivalent. Bonamy, Bousquet, Feghali, and Johnson asked if this holds when G is formed from the Cartesian product of C_m and C_n by adding parallel diagonals inside all 4-faces (this graph is of interest in statistical mechanics). We answer their question affirmatively when m,n ≥ 6.

This is joint work with Reem Mahmoud.

Vendredi 23 Avril à 14h - Arnaud de Mesmay
Optimally sweeping a planar graph, structure and complexity.
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

The Homotopy Height problem consists informally in finding the best way to sweep a planar graph using a homotopy (a continuous deformation) of a single connected closed curve, i.e., we want the length of the longest intermediate curve to be minimized. Such optimal homotopies are relevant for a wide range of purposes, from very mathematical questions in quantitative homotopy theory to more practical applications such as similarity measures for trajectories.

In this talk, we will survey what is known about this problem: the structure of the optimal solutions (simplicity, monotonicity), the complexity of solving it exactly and approximately, and its connections with grid minors.

Vendredi 16 Avril à 14h - William Lochet
Exploiting Dense Structures in Parameterized Complexity.
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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 http://perso.ens-lyon.fr/william.lochet/papers/dense_param.pdf

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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 : https://webconf.u-bordeaux.fr/b/mar-pmc-ht6

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

Program: https://www.lirmm.fr/~goncalves/JCRAALMA/index.php?n=Main.2021

Vendredi 26 Mars à 14h - Nacim Oijid
Complete coloring of signed graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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 ?
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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-
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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: https://webconf.u-bordeaux.fr/b/mar-ef4-zed 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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Abstract here