# 2020-2021

Vendredi 13 mai à **11h** - Frederik Garbe

Limits of Latin squares

**Only offline, no online version**

We introduce a limit theory for Latin squares, paralleling the recent limit theories of dense graphs and permutations. We define a notion of density, an appropriate version of the cut distance, and a space of limit objects – so-called Latinons. Key results of our theory are the compactness of the limit space and the equivalence of the topologies induced by the cut distance and the left-convergence. Last, using Keevash's recent results on combinatorial designs, we prove that each Latinon can be approximated by a finite Latin square.

This is joint work with Robert Hancock, Jan Hladký and Maryam Sharifzadeh.

Vendredi 6 mai à 14h - Quentin Deschamps

Metric Dimension on sparse graph

**Only offline, no online version**

The Metric Dimension problem consits in identifying vertices in a graph. The Metric Dimension of a graph G is the minimum cardinality of a subset S of vertices of G such that each vertex of G is uniquely determined by its distances to S. In a general case, add a vertex to a graph can drastically change its metric dimension, we prove we can bound this gap when the initial graph is the tree and one add several edges. To prove this result, we built a valid (but not minimal) set S which size can be bounded efficiently if the graphe is sparse enough.

Joint work with Nicolas Bousquet, Aline Parreau and Ignacio Pelayo

Vendredi 29 avril à 14h - Amedeo Sgueglia

Multistage Maker-Breaker Games

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We consider a new procedure, which we call Multistage Maker-Breaker Game. Maker and Breaker start from $G_0:=K_n$ and play several stages of a usual Maker-Breaker game where, for $i \ge 1$, the $i$-th stage is played as follows. They claim edges of $G_{i-1}$ until all edges are distributed, and then they set $G_i$ to be the graph consisting only of Maker's edges. They will then play the next stage on $G_i$.

This creates a sequence of graphs $G_0 \supset G_1 \supset G_2 \supset \dots$ and, given a monotone graph property, the question is how long Maker can maintain it, i.e. what is the largest $k$ such that Maker has a strategy to guarantee that $G_k$ satisfies such property. We will answer this question for several graph properties and pose a number of interesting questions that remain open.

This is joint work with Juri Barkey, Dennis Clemens, Fabian Hamann, and Mirjana Mikalački.

Vendredi 22 avril à 14h - Tassio Naia Dos Santos

Seymour's second neighbourhood conjecture, for almost every oriented graph.

**Only offline, no online version**

A famous conjecture of Seymour, known as Second Neighborhood Conjecture (SNC), says that every orientation of a graph contains a vertex whose second neighborhood is as large as its first neighborhood. I will present some recent results about the conjecture in the context of random graphs with either typical or arbitrary orientations.

Vendredi 8 avril à 14h - Jozef Skokan

Monochromatic partitions of graphs and hypergraphs.

**Only offline, no online version**

As a variant on the traditional Ramsey-type questions, there has been a lot of research about the existence of spanning monochromatic subgraphs in complete edge-coloured graphs and hypergraphs. One of the central questions in this area was proposed by Lehel around 1979, who conjectured that the vertex set of every 2-edge-coloured complete graph can be partitioned into two monochromatic cycles of distinct colours. This was answered in the affirmative by Bessy and Thomassé in 2010. Similar partitioning problems have been considered for more colours and for other graphs and hypergraphs.

In this talk we will review some of these problems and offer some results, proofs, and open questions.

Vendredi 1 avril à 14h - Laurent Feuilloley

A tour of local certification and its connection to other fields.

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

A local certification is basically a labeling of a graph G, that can convince the vertices that G has some property (eg "G is planar"). It originates from the study of fault-tolerance in distributed computing, but it is also an interesting object from a graph theory perspective. For example, the minimum amount of information that is required to certify a graph class can be seen as an (inverse) measure of the locality of this class.

In this talk I will introduce the notion, and give a tour of some recent techniques and questions, highlighting the relations to other fields such as communication complexity, (simple) graph decompositions, regular automata, graph colorings etc.

Vendredi 25 mars à 14h - Daniel Cranston

Kempe Equivalent List Colorings

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

An $\alpha,\beta$-Kempe swap in a properly colored graph interchanges the colors on some component of the subgraph induced by colors $\alpha$ and $\beta$. Two $k$-colorings of a graph are $k$-Kempe equivalent if we can form one from the other by a sequence of Kempe swaps (never using more than $k$ colors). Las Vergnas and Meyniel showed that if a graph is $(k-1)$-degenerate, then each pair of its $k$-colorings are $k$-Kempe equivalent. Mohar conjectured the same conclusion for connected $k$-regular graphs. This was proved for $k=3$ by Feghali, Johnson, and Paulusma (with a single exception $K_2\dbox K_3$, also called the 3-prism) and for $k\ge 4$ by Bonamy, Bousquet, Feghali, and Johnson.

In this paper we prove an analogous result for list-coloring. For a list-assignment $L$ and an $L$-coloring $\vph$, a Kempe swap is called $L$-valid for $\vph$ if performing the Kempe swap yields another $L$-coloring. Two $L$-colorings are called $L$-equivalent if we can form one from the other by a sequence of $L$-valid Kempe swaps. Let $G$ be a connected $k$-regular graph with $k\ge 3$. We prove that if $L$ is a $k$-assignment, then all $L$-colorings are $L$-equivalent (again excluding only $K_2\box K_3$). When $k\ge 4$, the proof is completely self-contained, implying an alternate proof of the result of Bonamy et al.

This is joint work with Reem Mahmoud.

Vendredi 18 mars à 14h - Colin Geniet

Twin-Width of groups and graphs of bounded degree

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Twin-Width is a graph invariant introduced by Bonnet, Kim, Thomassé, and Watrigant, with applications in logic, FPT algorithms, etc. Although twin-width is designed for dense graphs, we study it in the context of graphs of bounded degree. It is known that the class of graphs of twin-width k is small: it contains n! c^n graphs on vertices 1,...,n for some constant c. This implies that almost all d-regular graphs have twin-width more than k for any fixed k and d≥3. However no explicit constructions of graphs with bounded degree and unbounded twin-width is known.

For infinite graphs of bounded degree, finiteness of twin-width is preserved by quasi-isometries, i.e. functions which preserve distances up to affine upper and lower bounds. This allows to define `finite twin-width' on finitely generated group groups: given a group Γ finitely generated by S, the Cayley graph of Γ has vertices Γ, with an edge x–x·s for all x in Γ, s in S. This graph depends on the choice of S, but all Cayley graphs of Γ are quasi-isometric, hence one can say that Γ has finite twin-width if (all) its Cayley graphs do. Abelian groups, nilpotent groups, groups with polynomial growth have finite twin-width. Using an embedding theorem of Osajda, we construct a finitely generated group with infinite twin-width. This implies the existence of a small class of finite graphs with unbounded twin-width, a question raised in previous work.

This is joint work with Édouard Bonnet, Romain Tessera, Stéphan Thomassé.

Vendredi 25 février à 14h - Claire Hilaire

Long induced paths in minor-closed graph classes and beyond

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

In this work we show that every graph of pathwidth less than k that has a path of order n also has an induced path of order at least 1/3 n^{1/ k}. This is an exponential improvement and a generalization of the polylogarithmic bounds obtained by Esperet, Lemoine and Maffray (2016) for interval graphs of bounded clique number. We complement this result with an upper-bound.
This result is then used to prove the two following generalizations:

-every graph of treewidth less than k that has a path of order n contains an induced path of order at least 1/4 (log n)^{1/k};

- for every non-trivial graph class that is closed under topological minors there is a constant d∈(0, 1) such that every graph from this class that has a path of order n contains an induced path of order at least (log n)^{d}.

We also describe consequences of these results beyond graph classes that are closed under topological minors.

This is joint work with Jean-Florent Raymond (available at https://arxiv.org/pdf/2201.03880).

Vendredi 18 février à **13h30** - Linda Cook

Detecting a long even hole

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We call an induced cycle of even length in G an even hole. In 1991, Bienstock showed that it is NP-Hard to test whether a graph G has an even hole containing a specified vertex v in G. In 2002, Conforti, Cornuéjols, Kapoor and Vušković gave a polynomial-time algorithm to test whether a graph contains an even hole by applying a theorem about the structure of even-hole-free graphs from an earlier paper by the same group. In 2003, Chudnovsky, Kawarabayashi and Seymour provided a simpler polynomial time algorithm that searches for even holes directly. We extend this result by presenting a polynomial time algorithm to determine whether a graph has an even hole of length at least k for a given k ≥ 4. (Joint work with Paul Seymour)

Preprint at -- https://arxiv.org/abs/2009.05691

Vendredi 11 février à 14h - Marcin Briański

Separating polynomial χ-boundedness from χ-boundedness and thereabouts

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

If a graph contains no large complete subgraph but nonetheless has high chromatic number what can we say about the structure of such a graph? This question naturally leads to investigation of χ-bounded classes of graphs — graph classes where a graph needs to contain a large complete subgraph in order to have high chromatic number. This an active subfield of graph theory with many long standing open problems as well as interesting recent developments.

In this talk I will present a construction of a hereditary class of graphs which is χ-bounded but not polynomially χ-bounded. This construction provides a negative answer to a conjecture of Esperet that every χ-bounded hereditary class of graphs is polynomially χ-bounded. The construction is inspired by a recent paper of Carbonero, Hompe, Moore, and Spirkl which provided a counterexample to another conjecture of Esperet.

This is joint work with James Davies and Bartosz Walczak (available at https://arxiv.org/abs/2201.08814).

Vendredi 4 février à 14h - Florian Hörsch

Balancing spanning trees

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Given a graph G, a spanning tree of G is a subgraph T of G such that T is a tree and V (T ) = V (G). We investigate the question whether every graph that admits a packing of a certain number of spanning trees also admits such a packing where the spanning trees are balanced meaning that for every vertex v of the graph the degree of v in each of the spanning trees is ’roughly’ the same.
We first show how to solve this problems for a packing of two spanning trees. More concretely, we show that every graph G that admits a packing of two spanning trees also admits a packing of two spanning trees T1, T2 such that |dT1 (v) − dT2 (v)| ≤ 5 for all v ∈ V (G).
We further show that a similar statement also holds for spanning tree packings of arbitrary size, namely that every graph G that contains a packing of k spanning trees for some positive integer k also contains a packing of k spanning trees T1, . . . , Tk such that |dTi (v) − dTj (v)| ≤ ck for all v ∈ V (G) and i, j ∈ {1, . . . , k} where ck is a constant only depending on k.
This solves a conjecture of Kriesell.

Vendredi 28 janvier à 14h - Alp Muyesser

Transversals in graph collections

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Suppose we have a collection of graphs on a mutual vertex set, say V. A graph G on V is then called rainbow, if G uses at most one edge from each graph in the collection. Aharoni initiated the study of finding sufficient conditions for the existence of rainbow subgraphs in graph collections. Notably, he asked whether n graphs with minimum degree n/2 on a mutual vertex set of size n admit a rainbow Hamilton cycle. This is a far-reaching generalisation of Dirac's theorem, a cornerstone in graph theory.

We will talk about a general strategy for problems of this type that relies on a novel absorption argument. As an application, we will obtain rainbow versions of several classical theorems from extremal graph theory.

This is joint work with Richard Montgomery and Yani Pehova

Vendredi 21 janvier à 14h - Marek Sokołowski

Graphs of bounded twin-width are quasi-polynomially chi-bounded

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We prove that for every $t \in \N$ there is a constant $c_t$ such that every graph with twin-width at most $t$ and clique number $\omega$ has chromatic number bounded by $2^{c_t \log^{O(t)} \omega}$. In other words, we prove that graph classes of bounded twin-width are quasi-polynomially $\chi$-bounded. This provides a partial resolution of a conjecture of Bonnet et al. [SODA 2021] that they are polynomially $\chi$-bounded.

This is a joint work with Michal Pilipczuk.

Vendredi 14 janvier à 14h - Samuel Mohr

Uniform Turán density

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

In the early 1980s, Erdős and Sós initiated the study of the classical Turán problem with a uniformity condition:
the uniform Turán density of a hypergraph `H`

is the infimum over all `d`

for which
any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least `d`

contains `H`

.
In particular, they raise the questions of determining the uniform Turán densities of K_{4}^{(3)-} and K_{4}^{(3)}.
The former question was solved only recently in [Israel J. Math. 211 (2016), 349--366] and [J. Eur. Math. Soc. 97 (2018), 77--97],
while the latter still remains open for almost 40 years.
In addition to K_{4}^{(3)-}, the only 3-uniform hypergraphs whose uniform Turán density is known
are those with zero uniform Turán density classified by Reiher, Rödl and Schacht~[J. London Math. Soc. 97 (2018), 77--97] and
a specific family with uniform Turán density equal to 1/27.

In this talk, we give an introduction to the concept of uniform Turán densities, present a way to obtain lower bounds using color schemes, and give a glimpse of the proof for determining the uniform Turán density of the tight 3-uniform cycle C_{ℓ}^{(3)}, ℓ ≥ 5$.

Vendredi 7 janvier à 14h - Tom Davot

Une approche gloutonne pour l'échafaudage du génome

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

L'échafaudage est un problème en bio-informatique dont le but est de
compléter le processus d'assemblage de séquences génomiques (appelées contigs) en determinant leurs
positions et orientations relatives. Ce problème peut être vu comme un
problème de couverture par des cycles et des chemins d'un graphe
particulier appelé "graphe d'échafaudage". Dans cette présentation,
nous formulons quelques résultats sur la complexité de ce problème.
Nous adaptons également un algorithme glouton, formulé originellement
sur les graphes complets, afin qu'il fonctionne sur une classe
particulière que nous espérons plus proche des instances réelles.
Cet algorithme est le premier algorithme polynomial pour une classe différente des graphes complets.

Vendredi 17 décembre à 14h - Bruno Courcelle

The bounds of a class of graphs or hypergraphs

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

(Exposé en français. Transparents et questions en anglais)

A bound of a class of finite graphs C is a finite graph not in C whose proper induced subgraphs are all in C. In French «une borne de C», terminology by Fraïssé and Pouzet.
The questions are: is Bounds(C) finite? If yes compute it.
Which properties of Bounds(C) imply that C has bounded clique-width?
I will present the following tools:

1. Graph Theory «pedestrian» arguments possibly using TRAG software (trag.labri.fr) for checking clique-width.

2. Monadic Second-Order descriptions + upper-bounds to clique-width

3. Well-quasi order arguments, give finiteness but no effective list.

- A working example will be the class of *probe cographs*, extending that of cographs and having finitely many bounds.

- Also: MSO tools do not work for ternary hypergraphs, but wqo arguments may work.

A full article is available.

Vendredi 10 décembre à 10h - Dimitri Lajou

PhD defense: On various graph coloring problems.

A29, amphitheater

In this thesis, we study some graph coloring problems. We are interested in two families of colorings. The first one consists in coloring graphs, called signed graphs, modeling social links. These signed graphs dispose of two types of edges: positive edges to represent friendship and negative edges for animosity. Coloring signed graphs is done through the notion of homomorphism: the chromatic number of a signed graph (G, σ) is the smallest order of a signed graph (H, π) to which (G, σ) admits a homomorphism. We study the complexity of homomorphisms of signed graphs when the target graph is fixed and when the input can be modified, giving P/NP-complete dichotomies and FPT/W[1]-hard dichotomies. We also present bounds on the chromatic number of signed graphs when the input graph has few cycles. Finally, we study the relationship between homomorphisms of signed graphs and the Cartesian product of signed graphs. The second family of colorings consists in coloring edges, instead of vertices, according to some constraints. We study four kinds of edge-colorings notions: packing edge-colorings, injective edge-colorings, AVD colorings and 1-2-3-labellings. Packing edge-coloring is a form of proper edge-coloring where each color has its own conflict rule, for example, color 1 may behave according to the rules of proper edge-colorings while color 2 behave according to the rules of strong edge-colorings. We study packing edge-coloring on subcubic graphs and provide bounds on the number of colors necessary to color the graphs. An injective edge-coloring is an edge-coloring where for any path of length 3, the two non-internal edges of the path receive different colors. We determine the complexity of injective edge-coloring for some classes of graphs. For AVD colorings, i.e. a proper edge-coloring where adjacent vertices are incident with different sets of colors, we obtain bounds on the number of colors required to color the graph when the graph has its maximum degree significantly greater than its maximum average degree and when the graph is planar and has maximum degree at least 12. Finally, we prove the Multiplicative 1-2-3 Conjecture, i.e. that every connected graph (which is not just an edge) can be edge-labelled with labels 1, 2 and 3 so that the coloring of G, obtained by associating with each vertex the product of the labels on edges incident with u, is proper.

Vendredi 10 décembre à 14h - Jacob Cooper

Uniform Turan density

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

In the early 1980s, Erdos and Sos initiated a study of the classical Turan problem with an additional uniformity condition: the uniform Turan density of a k-uniform hypergraph H is the infimum over all d for which any sufficiently large hypergraph with the property that every linear-size subhypergraph has density at least d contains H. In particular, they raised the question of determining the uniform Turan densities of K_4^(3) (the complete 3-uniform hypergraph on four vertices) and K_4^{(3)-} (the complete 3-uniform hypergraph on four vertices minus an edge). The latter question was solved only recently in [Israel J. Math. 211 (2016), 349--366] and [J. Eur. Math. Soc. 97 (2018), 77--97], whilst the former continues to be open, now for almost 40 years. In addition to K_4^{(3)-}, the only 3-uniform hypergraphs whose uniform Turan density is known are those with uniform Turan density equal to zero, as classified by Reiher, Rodl and Schacht [J. London Math. Soc. 97 (2018), 77--97], and a specific family with uniform Turan density equal to 1/27.

In this talk, we will give a self-contained introduction to the concept of uniform Turan densities, present a way to obtain lower bounds using so-called colour schemes, and give a glimpse of the proof for determining the uniform Turan density of the tight 3-uniform cycle C_\ell^(3), for \ell\geq 5. Based on joint work with Matija Bucic, David Correia, Daniel Kral and Samuel Mohr.

Lundi 13 décembre à 14h - Alexandre Blanché

PhD defense: Décomposition en chemins de Gallai dans les graphes planaires

Labri, amphitheater

Cette thèse s’inscrit dans le domaine de la théorie des graphes, et traite d’une question posée en 1968 par Tibor Gallai, toujours sans réponse aujourd’hui. Gallai conjectura que les arêtes de tout graphe connexe à n sommets pouvaient être partitionnées en ⌈n/2⌉ chemins. Bien que cette conjecture fut attaquée et partiellement résolue au fil des ans, la propriété n’a été prouvée que pour des classes de graphes très spécifiques, comme les graphes dont les sommets de degré pair forment une forêt (Pyber, 1996), les graphes de degré maximum 5 (Bonamy, Perrett, 2016) ou les graphes de largeur arborescente au plus 3 (Botler, Sambinelli, Coelho, Lee, 2017). Les graphes planaires sont les graphes qui peuvent être plongés dans le plan, c’est-à-dire dessinés sans croisements d’arêtes. C’est une classe bien connue dans la théorie des graphes, et largement étudiée. Botler, Jiménez et Sambinelli ont récemment confirmé la conjecture dans le cas des graphes planaires sans triangles. Notre résultat consiste en une preuve de la conjecture sur la classe générale des graphes planaires. Cette classe est notablement plus générale que celles des précédents résultats, et de notre point de vue constitue une importante contribution à l’étude de la conjecture de Gallai. Plus précisément, nous travaillons sur une version plus forte de la conjecture, proposée par Bonamy et Perrett en 2016, et qui énonce que les graphes connexes à n sommets peuvent être décomposés en ⌊n/2⌋ chemins, à l’exception d’une famille de graphes denses. Nous confirmons cette conjecture dans le cas des graphes planaires, en démontrant que tout graphe planaire à n sommets, à l’exception de K3 et de K5 − (K5 moins une arête), peut être décomposé en ⌊n/2⌋ chemins. La preuve est divisée en trois parties : les deux premières montrent le lemme principal de la preuve, qui restreint la structure d’un contre-exemple hypothétique ayant un minimum de sommets, et la troisième partie utilise ce lemme pour montrer qu’un tel contre-exemple n’existe pas.

Vendredi 26 novembre à 14h - Sanjana Dey & Subhadeep Dev

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Sanjana Dey: Discriminating Codes in Geometric Setups. 14h

We study geometric variations of the discriminating code problem. In the discrete version of the problem, a finite set of points P and a finite set of objects S are given in R^d. The objective is to choose a subset S^* \subseteq S of minimum cardinality such that for each point p_i in P the subset S_i^* \subseteq S^* covering p_i, satisfy S_i^*\neq \emptyset, and each pair p_i,p_j in P, i \neq j, satisfies S_i^* \neq S_j^*. In the continuous version of the problem, the solution set S^* can be chosen freely among a (potentially infinite) class of allowed geometric objects.

In the 1-dimensional case, d=1, the points in P are placed on a line L and the objects in S are finite-length line segments aligned with L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in one dimension. Still, for the 1-dimensional discrete version, we design a polynomial-time 2-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length.

We then study the 2-dimensional case, d=2, for axis-parallel unit square objects. We show that the continuous version is NP-complete, and design a polynomial-time approximation algorithm that produces (8+\epsilon)-approximate solutions, using rounding of suitably defined integer linear programming problems.

Subhadeep Dev: The k-Center Problem on Cactus Graphs. 14h55

The weighted k-center problem in graphs is a classical facility location problem where we place k centers on the graph which minimize the maximum weighted distance of a vertex to its nearest center. We study this problem when the underlying graph is a cactus with n vertices and present an O(n log^2 n) time algorithm for the same. This time complexity improves upon the O(n^2) time algorithm by Ben-Moshe et al. [TCS, 2007] which was the previous state of the art. We achieve this improvement by introducing methods to generalize Frederickson’s [SODA, 1991] sorted matrix technique to cactus graphs. The existence of a subquadratic al-gorithm for this problem was open for more than a decade.

Lundi 14 au Vendredi 19 - JGA

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Vendredi 12 novembre à 14h - Stijn Cambie

Maximising line subgraphs of diameter at most t

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We consider an edge version of the famous (and hard) degree-diameter problem, where one is wondering about the maximum size of a graph given maximum degree and diameter of the line graph. This problem originated from 1988 and was proposed by Erdos and Nesetril. It was the inspiration for a series of research papers on variants of this problem. We will start discussing part of the history, which is related with e.g. the (still widely open) strong edge colouring conjecture. In the second part of the talk, we will look again to the initial inspirational question and the ideas behind some progress on this.

Vendredi 5 novembre à 14h - Maria Chudnovsky

Induced subgraphs and logarithmic tree width

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Tree decompositions are a powerful tool in structural graph
theory; they are traditionally used in the context of forbidden graph minors.
Connecting tree decompositions and forbidden induced subgraphs has until
recently remained out of reach.

Tree decompositions are closely related to the existence of "laminar
collections of separations" in a graph, which roughly means that the
separations in the collection ``cooperate'' with each other, and the pieces
that are obtained when the graph is simultaneously decomposed by all the
separations in the collection ``line up'' to form a tree structure.
Such collections of separations come up naturally in the context of forbidden
minors.

In the case of families where induced subgraphs are excluded, while there
are often natural separations, they are usually very far from forming a
laminar collection. However, under certain circumstances, these
collections of natural separations can be partitioned into a number of
laminar collections, and the number of laminar collections needed is
logarithmic in the number of vertices of the graph. This in turn allows us
to obtain a wide variety of structural and algorithmic results, which we
will discuss in this talk.

Vendredi 29 octobre à 14h - Hoang La

Further Extensions of the Grötzsch Theorem

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

The Grötzsch Theorem states that every triangle-free planar graph admits a proper 3-coloring. Among many of its generalizations, the one of Grünbaum and Aksenov, giving 3-colorability of planar graphs with at most three triangles, is perhaps the most known. A lot of attention was also given to extending 3-colorings of subgraphs to the whole graph. In this paper, we consider 3-colorings of planar graphs with at most one triangle. Particularly, we show that precoloring of any two non-adjacent vertices and precoloring of a face of length at most 4 can be extended to a 3-coloring of the graph. Additionally, we show that for every vertex of degree at most 3, a precoloring of its neighborhood with the same color extends to a 3-coloring of the graph. The latter result implies an affirmative answer to a conjecture on adynamic coloring. All the presented results are tight.

Vendredi 22 octobre à 14h - Bartosz Walczak

Distinguishing classes of intersection graphs of homothets or similarities of two convex disks

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

For smooth convex disks A, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes Ghom(A) and Gsim(A) of intersection graphs that can be obtained from homothets and similarities of A, respectively. Namely, we prove that Ghom(A)=Ghom(B) if and only if A and B are affine equivalent, and Gsim(A)=Gsim(B) if and only if A and B are similar.

Joint work with Mikkel Abrahamsen.

Vendredi 15 octobre à 14h - Clément Legrand-Duchesne

On a recolouring version of Hadwiger's conjecture

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We prove that for any epsilon > 0, for any large enough t, there is a graph G that admits no Kt-minor but admits a (3/2 - epsilon)t-colouring that is "frozen" with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.

Vendredi 8 octobre à 14h - Tassio Naia Dos Santos

Three questions about graphs of large chromatic number

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Let G be an arbitrary graph with chromatic number k, where k is
large. We discuss the state of the art of the following three
open questions.

Erdős and Neumann-Lara (1979): does G admit an orientation with "high" dichromatic number? (The dichromatic number is the smallest size of a vertex partition in which each part induces an acyclic digraph.)

Burr (1980): is it true that every orientation of G contains all oriented trees of order k/2 +1 ?

Bukh (2015 or earlier): Is it true that typical subgraphs of G have chromatic number at least ck/log k for some positive constant c, independent of k ?

Vendredi 1 octobre à **15h** - Nicole Wein

Token Swapping on Trees

Connexion: **https://u-bordeaux-fr.zoom.us/j/4939941120**

In the token swapping problem, we are given a graph with a labeled token on each vertex along with a final configuration of the tokens, and the goal is to find the minimum number of swaps of adjacent tokens to reach the final configuration. Token swapping is in the area of "Reconfiguration Problems" where the goal is generally to get from an initial configuration to a final configuration using a step-by-step series of changes. I will talk about both algorithms and hardness for the token swapping problem, mostly focusing on the case where the underlying graph is a tree.

Vendredi 24 septembre à 14h - Oliver Janzer

Counting H-free orientations of graphs.

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

In 1974, Erdős posed the following problem. Given an oriented graph H, determine or estimate the maximum possible number of H-free orientations of an n-vertex graph. When H is a tournament, the answer was determined precisely for sufficiently large n by Alon and Yuster. In general, when the underlying undirected graph of H contains a cycle, one can obtain accurate bounds by combining an observation of Kozma and Moran with celebrated results on the number of F-free graphs. We resolve all remaining cases in an asymptotic sense, thereby giving a rather complete answer to Erdős's question. Moreover, we determine the answer exactly when H is an odd cycle and n is sufficiently large, answering a question of Araújo, Botler and Mota.

Joint work with Matija Bucic and Benny Sudakov.

Vendredi 17 septembre à 14h - Julien Bensmail

A proof of the Multiplicative 1-2-3 Conjecture.

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We prove that the product version of the 1-2-3 Conjecture, raised by Skowronek-Kaziów in 2012, is true. Namely, for every connected graph with order at least 3, we prove that we can assign labels 1,2,3 to the edges in such a way that no two adjacent vertices are incident to the same product of labels.

This is joint work with Hervé Hocquard, Dimitri Lajou and Éric Sopena.

Vendredi 3 septembre à 14h - Alexandra Wesolek

A tight local algorithm for the minimum dominating set problem in outerplanar graphs. / Limiting crossing numbers.

Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

A tight local algorithm for the minimum dominating set problem in outerplanar graphs
We present a deterministic local algorithm which computes a 5-approximation of a minimum dominating set on outerplanar graphs, and show that this is optimal. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed.

This is joint work with Marthe Bonamy, Linda Cook and Carla Groenland.

Limiting crossing numbers
In this talk we will explain a set up which shows that the theory of graph limits introduced by Lovász et al. can be applied to intersection graphs of graph drawings. We consider a model of random, geodesic drawings of the complete bipartite graph Kn,n on the unit sphere and show that the intersection graphs form a convergent series (for n going to infinity).

This talk is based on joint work with Marthe Bonamy and Bojan Mohar.

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