Groupe

# 2021-2022

Vendredi 24 juin à 14h - Nathanaël Fijalkow
Universal graphs for playing games
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

I will introduce the notion of universal graphs for playing games: they are similar in spirit to the usual notion, but parameterised by an additional condition, such as (for weighted graphs) "all cycles have non negative total weights". I will briefly show what are their applications (algorithms for model checking games), and then focus on the combinatorial questions: understanding the size of minimal universal graphs.

This talk will survey a number of more or less recent results jointly obtained with Thomas Colcombet, Pierre Ohlmann, and Paweł Gawrychowski.

Vendredi 17 juin à 14h - František Kardoš
Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
Let G be a bridgeless cubic graph. The Berge-Fulkerson Conjecture (1970s) states that G admits a list of six perfect matchings such that each edge of G belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan-Raspaud Conjecture (1994), which states that G admits three perfect matchings such that every edge of G belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that G admits two perfect matchings whose deletion yields a bipartite subgraph of G. It can be shown that given an arbitrary perfect matching of G, it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan-Raspaud and the Berge-Fulkerson conjectures, respectively. In this talk, we show that given any 1+-factor F (a spanning subgraph of G such that its vertices have degree at least 1) and an arbitrary edge e of G, there always exists a perfect matching M of G containing e such that G∖(F∪M) is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in G, there exists a perfect matching of G containing at least one edge of each circuit in this collection.

This is a joint work with Edita Máčajová and Jean Paul Zerafa.

Vendredi 03 juin à 14h - Alp Muyesser
Rainbow matchings in groups
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
A rainbow matching in an edge-coloured graph is a matching whose edges all have different colours. Let G be a group of order n and consider an edge-coloured complete bipartite graph, whose parts are each a copy of the group G, and the edge (x, y) gets coloured by the group element xy. We call this graph the multiplication table of G. For which groups G does the multiplication table of G have a rainbow matching? This is an old question in combinatorial group theory due to Hall and Paige, with close connections to the study of Latin squares. The problem has been resolved in 2009 with a proof relying on the classification of finite simple groups. In 2021, a "simpler" proof for large groups appeared, this time using tools from analytic number theory. We present a third resolution of this problem, again only for large groups, and using techniques from probabilistic combinatorics. The main advantage of our approach is that we are able to find rainbow matchings in random subgraphs of the multiplication table of G. This flexibility allows us to settle numerous longstanding conjectures in this area. For example, Evans asked for a characterisation of groups whose elements can be ordered so that the product of each consecutive pair of elements is distinct. Using our results, we are able to answer this question for large groups. In this talk, we will give a gentle survey of this area. This is joint work with Alexey Pokrovskiy.

Vendredi 20 mai à 14h -
On asymptotic packing of geometric graphs
Only offline, no online version

A geometric graph G is a graph drawn in the Euclidean plane such that its vertices are points in general position and its edges are drawn as straight line segments. Given a complete geometric graph H_n on n vertices, we are interested in finding a large collection of plane copies of a graph G in H_n such that each edge of H_n appears in at most one copy of G. We say a graph G is geometric-packable if for every sequence of geometric complete graphs $(H_n)_{n \geq 1}$ all but o(n^2) edges of H_n can be packed by plane copies of G. In a joint work with Daniel W. Cranston, Jiaxi Nie and Jacques Verstraete, we study geometric-packability and show that if G is a triangle, plane 4-cycle or plane 4-cycle with a chord, the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions).

Vendredi 13 mai à 11h -
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 -
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 n1/ 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 K4(3)- and K4(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 K4(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.

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:

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.