Groupe

# 2020-2021

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. 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: 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 toK_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 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