{"id":145,"date":"2025-05-06T08:48:57","date_gmt":"2025-05-06T08:48:57","guid":{"rendered":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/?page_id=145"},"modified":"2026-10-01T08:01:23","modified_gmt":"2026-10-01T08:01:23","slug":"grapheslyon","status":"publish","type":"page","link":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/grapheslyon\/","title":{"rendered":"Graphes@Lyon"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Graphes@Lyon is the graph theory seminar jointly organized by the MC2 team at LIP and the <a href=\"https:\/\/liris.cnrs.fr\/equipe\/goal\" data-type=\"link\" data-id=\"https:\/\/liris.cnrs.fr\/equipe\/goal\">GOAL<\/a> team at LIRIS.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Local organizers: <a href=\"https:\/\/perso.liris.cnrs.fr\/nbousquet\/\" data-type=\"link\" data-id=\"https:\/\/perso.liris.cnrs.fr\/nbousquet\/\">Nicolas Bousquet<\/a> (LIRIS) and <a href=\"https:\/\/perso.univ-lyon1.fr\/remi.watrigant\" data-type=\"link\" data-id=\"https:\/\/perso.univ-lyon1.fr\/remi.watrigant\">R\u00e9mi Watrigant<\/a> (MC2). Contact us if you want to give a talk!<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Upcoming talks<\/h2>\n\n\n\n<h5 class=\"wp-block-heading\">Linda Kleist (Univ. Hambourg) and Joseph Dorfer (TU Graz)<\/h5>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 01\/10\/26 at 14:00<\/li>\n\n\n\n<li>Where: LIRIS<\/li>\n\n\n\n<li>Who: Linda Kleist (Univ. Hambourg) and Joseph Dorfer (TU Graz)<\/li>\n\n\n\n<li>What: <\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Joseph Dorfer&nbsp;<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Title:<\/strong> Flip distance between triangulations of a convex polygon.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract:<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Triangulations of a convex (n+2)-gon are famously counted by the n-th Catalan number, and so are binary trees on n internal nodes. Consequently, there exists a bijection between the triangulations of convex polygons and binary trees of the right sizes.<br>One way to transform one triangulation into another is via an edge flip, that is, an operation that replaces one diagonal in a convex quadrilateral with the other diagonal. To transform a binary tree into another, one can perform a rotation that exchanges an internal node with its parent node and reattaches the subtrees rooted at those two nodes.&nbsp;The standard bijection between triangulations of convex polygons and binary trees preserves incidence under these reconfiguration operations. If two triangulations only differ by a single edge flip, then their corresponding binary trees only differ in a single rotation.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The complexity of determining the minimum number of rotations that transform one binary tree into another&nbsp;(or the equivalent problem for triangulations) has been raised as an open problem by Culik and Wood in 1982. It was popularized through the study of extremal pairs of triangulations by Sleator, Tarjan, and Thurston in 1986.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">We settle this open problem by proving that the flip distance problem for triangulations of convex polygons is NP-complete.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Linda Kleist&nbsp;<br><br>Title:<\/strong> Online Packing and Online Sorting Problems<br><br><strong>Abstract:<\/strong> Packing problems arise on a daily basis\u2014organizing a kitchen drawer, baking cookies, cutting fabric, packing a suitcase, or loading a car. Similar problems appear in industrial settings such as shipping, the clothing industry, and logistics. In this talk, we study translational online packing problems, where items arrive one by one and must be placed irrevocably into a strip (or into bins, a square, or the plane).&nbsp; The goal is to minimize resource usage, such as the strip width.&nbsp;<br><br>While online algorithms with a constant competitive ratio have been known for rectangles for decades, the theoretical foundations for more complex objects are much less understood.&nbsp; In joint work with Aamand, Abrahamsen, and Beretta [SODA 2023], we prove a lower bound of&nbsp; \\Omega(\\sqrt{\\log n\/\\log\\log n}) on the competitive ratio of any online strip packing algorithm for convex polygons. Very recently, together with Aamand, Abrahamsen, Bartlmae, Khan, and T\u00f3th, we present an O(\\log^2 n)-competitive algorithm for online translational strip packing of convex polygons, improving upon the previous algorithm with competitive ratio O(n^.59).&nbsp;<br><br>With Gerlach and Hennies [SoCG 2026], we study online packing of orthogonal polygons and show that the competitive ratio one any online algorithm that aims to orthogonal 6-gons into a minimal number of unit bins is in \\Omega(n\/\\log n). Already for 8-gons, we show that the trivial n-competitive algorithm, which places each item in its own bin, is best-possible.&nbsp;<br><br>Interestingly, the insights are gained through three different online sorting problems. In this talk, we discuss these packing problems and their connections to natural online sorting problems.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">TBA<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 15\/10\/26 at 14:30<\/li>\n\n\n\n<li>Where: LIRIS<\/li>\n\n\n\n<li>What: TBA<\/li>\n\n\n\n<li>Abstract: TBA<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">TBA<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 12\/11\/26 at 14:30<\/li>\n\n\n\n<li>Where: LIP<\/li>\n\n\n\n<li>What: TBA<\/li>\n\n\n\n<li>Abstract: TBA<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">TBA<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 26\/11\/26 at 14:30<\/li>\n\n\n\n<li>Where: LIRIS<\/li>\n\n\n\n<li>What: TBA<\/li>\n\n\n\n<li>Abstract: TBA<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">TBA<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 10\/12\/26 at 14:30<\/li>\n\n\n\n<li>Where: LIP<\/li>\n\n\n\n<li>What: TBA<\/li>\n\n\n\n<li>Abstract: TBA<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Past talks<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Eva Rotenberg<\/strong> (<strong>ITU Copenhagen<\/strong>, Denmark)<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 29\/06\/26 at 10am<\/li>\n\n\n\n<li>Where: TD5 (ground floor of the Nautibus building)<\/li>\n\n\n\n<li>What: Whether a Graph Admits a Vertex that Lies in All Longest Paths is \u03982-Complete<\/li>\n\n\n\n<li>Abstract: <br>When a graph admits a vertex v that is contained in all its longest paths, we call v a <em>Gallai vertex<\/em>. These are named after Gallai, who in 1969 asked the question if it is true that every connected graph contains such a vertex. This was soon answered in the negative by Walther and Zamfirescu, who presented a graph in which every vertex is omitted by some longest path of the graph.<br><br>Inspite of its long history, the Gallai Vertex Problem, i.e. determining whether a graph has a Gallai vertex, was until now not known to be neither NP- nor coNP-hard. In this work, we show something much stronger, as we completely settle the computational complexity of determining whether a graph has a Gallai vertex: We show that it is complete for the complexity class \u0398_2^p = P^(NP[log n]).<br>This class, also known as &#8220;parallel access to NP&#8221;, is a complexity class larger than NP situated just below the class \u03a3_2^p in Stockmeyer&#8217;s polynomial hierarchy.<br><br>In more generality, the <em>longest path transversal number<\/em> of a connected graph is the minimum size of a set of vertices that intersects all its longest paths. I.e. if the graph has a Gallai vertex, its longest path transversal number is 1. Thus, as a consequence of our theorem, the longest path transversal number of a graph cannot be approximated in polynomial time by a factor better than 2, unless P=NP. In fact, using related techniques, we show a strengthening of this result: For any constant C, if there is a graph with longest path transversal number C, then there is no polynomial time algorithm for approximating the longest path transversal number by a factor better than C, unless P = NP. In particular, this excludes approximation by a factor below 3. Similar results hold for the longest cycle transversal.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Claire Hilaire (Universit\u00e9 Clermont Auvergne)<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 29\/06\/26 at 10:45am<\/li>\n\n\n\n<li>Where: TD5 (ground floor of the Nautibus building)<\/li>\n\n\n\n<li>What: Maximal order of planar graphs of small diameter<\/li>\n\n\n\n<li>Abstract:<br>The degree diameter problem asks for the maximum possible number of vertices in a graph of maximum degree $\\Delta$ and diameter $D$. In this paper, we focus on planar graphs of diameter $3$. Fellows, Hell and Seyffarth (1995) proved that for all $\\Delta\\geq 8$, the maximum number $\\np_{\\Delta, D}$ of vertices of a planar graph with maximum degree at most $\\Delta$ and diameter at most 3 satisfies $\\frac{9}{2}\\Delta &#8211; 3 \\leq \\np_{\\Delta,3} \\leq 8 \\Delta + 12$. We show that the lower bound they gave is optimal, up to an additive constant, by proving that there exists $c&gt;0$ such that $\\np_{\\Delta,3} \\leq \\frac{9}{2}\\Delta + c$ for every $\\Delta\\geq 0$. Our proof consists in a reduction to the fractional maximum matching problem on a specific class of planar graphs.<br>Joint work with Antoine Dailly, Sasha Darmon, Ugo Giocanti and Petru Valic<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Ioan Todinca (Universit\u00e9 Orl\u00e9ans)<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 30\/06\/26 at 10:30am<\/li>\n\n\n\n<li>Where: Amphi B, ENS de Lyon<\/li>\n\n\n\n<li>What: What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing<\/li>\n\n\n\n<li>Abstract:<br>Algorithmic meta-theorems are results of the form \u201cevery computational problem that can be formalised in a given logic L can be solved e\ufb03ciently on every class C of [graphs] satisfying certain conditions\u201d [Kreutzer 2011].&nbsp;They have become central to classical (sequential) graph theory since Courcelle\u2019s theorem in the 1990s, with numerous recent developments, particularly on first-order logic. We are currently witnessing the gradual introduction of algorithmic meta-theorems into distributed computing, initiated by [Feuilloley, Bousquet,&nbsp;Pierron, PODC 2022].<br>My presentation will begin with an easily accessible introduction to distributed computing, in particular to the CONGEST model, in which the nodes of a network communicate in synchronous rounds by exchanging \u201csmall\u201d messages (of logarithmic size) with their neighbours. The aim is to collectively solve a task in a small number of rounds. We shall see that, in distributed computing, even the decision of simple properties such as \u201cthe graph has no 4-vertex cycle\u201d or \u201cthe graph has at most one&nbsp;vertex of degree 3\u201d encounters barriers of congestion or (non-)locality. Both problems are expressible in on first-order logic (FO).<br>In the second part, I will discuss the decision of FO problems in graph classes of bounded expansion. We shall see that sequential FO model-checking extends to the CONGEST model, in O(Diameter + log n) rounds, notably thanks to the low tree-depth colouring tools for these classes. For local FO formulas f(x) (whose truth depends only on a ball of constant radius around x, such as \u201cx has a twin\u201d), we have shown that all vertices satisfying the formula can be marked in O(log n) rounds, answering a question posed by [Ne\u0161et\u0159il, Ossona de Mendez, Distributed Computing 2016].&nbsp;<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Maxime Flin (<strong>Aalto University, Finland<\/strong>)<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 25\/06\/2026<\/li>\n\n\n\n<li>Where: Nautibus, La Doua<\/li>\n\n\n\n<li>Who: Maxime Flin (Aalto University, Finland)<\/li>\n\n\n\n<li>What: Distributed and semi-streaming coloring<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Graph meetings <\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">in memory of Carl Feghali<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 18\/06\/2026<\/li>\n\n\n\n<li>Where: LIP, amphi B<\/li>\n\n\n\n<li>Who: everyone<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Fanny Hauser (LaBRI, Bordeaux)<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 21\/05\/2026<\/li>\n\n\n\n<li>Where: LIP, amphi B<\/li>\n\n\n\n<li>Who: Fanny Hauser (LaBRI, Bordeaux)<\/li>\n\n\n\n<li>What: Tree-independence through distance to chordal graphs<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract:<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The tree-independence number of a graph is the analogue of treewidth where, instead of minimising the size of bags, we minimise the size of a stable set contained in a bag. Chordal graphs have tree-independence 1, and it remains an active line of research to determine the tree-independence of various graph classes \u2014 or even to establish whether it is bounded in general. We show that graphs with no induced&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">C4 nor P1 +P4&nbsp; have tree-independence at most 2 by proving a conjecture of Hilaire, Milani\u010d, and Vasi\u0107 (2025) stating that they can be made chordal by deleting a clique. This is joint work with Marthe Bonamy and Sarah Houdaigoui.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Graph Meetings : Clara Marcille and Nicolas Bousquet<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 05\/05\/2026<\/li>\n\n\n\n<li>Where: LIRIS, room TBA<\/li>\n\n\n\n<li>Who: Clara Marcille (MC2, LIP) and Nicolas Bousquet (GOAL, LIRIS)<\/li>\n\n\n\n<li>What: Monitoring edge-geodetics of graphs <\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Graph Meetings : Felicia Lucke (LIP) and Yannick Mogge (LIRIS)<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">First talk<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Who: Felicia Lucke (MC2, LIP)<\/li>\n\n\n\n<li>What: Optimising Matching Cuts &#8211; Why Maximising is Harder than Minimising<\/li>\n\n\n\n<li>Abstract: The problem Matching Cut asks for an edge set of a graph which is both an edge cut and a matching. We consider the two recent optimisation variants Maximum and Minimum Matching Cut, where we aim to maximise respectively minimise the number of edges in the matching cut. Both variants are NP-hard but differ in complexity for certain graph classes. In this talk we investigate why maximising is harder than minimising. We further compare the optimisation variants of Matching Cut to the classical Matching Cut and its oldest variant Perfect Matching Cut.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Second Talk<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Who: Yannick Mogge (GOAL, LIRIS)<\/li>\n\n\n\n<li>What: Cops and Cleaners with limited visibility<\/li>\n\n\n\n<li>Abstract: We consider the model of limited visibility Cops and Robbers, where the cops can only see within their $l$-neighbourhood. We prove that the gap between the number of cops needed to see the robber and the number of cops needed to capture the robber can be arbitrarily large, answering an open question from the literature. We also consider how close we can get to seeing the robber when we do not have enough cops available.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Alp M\u00fcyesser : Cycle-factors of regular graphs via entropy<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: <s>09\/04\/2024 at 14:00<\/s> Cancelled<\/li>\n\n\n\n<li>Where: LIP, amphi A (to be confirmed)<\/li>\n\n\n\n<li>Who: Alp M\u00fcyesser (New College, University of Oxford)<\/li>\n\n\n\n<li>What: Cycle-factors of regular graphs via entropy<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract:<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">It is a classical result that a random permutation of n elements has, on average, about \\log n cycles. We generalise this fact to all directed d-regular graphs on n vertices by showing that, on average, a random cycle-factor of such a graph has O((n\\log d)\/d) cycles. This is tight up to the constant factor and improves the best previous bound of the form O(n\/\\sqrt{\\log d}) due to Vishnoi. Our results also yield randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length (1+O((\\log d)\/d)) \\cdot n if the graph is connected. This makes progress on a conjecture of Magnant and Martin and on a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close. Joint work with Micha Christoph, Nemanja Dragani\u0107, Ant\u00f3nio Gir\u00e3o, Eoin Hurley and Lukas Michel.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Ma\u00ebl Dumas: Variants of Merge-Width and Applications<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 12\/03\/2026 at 14:00<\/li>\n\n\n\n<li>Where: LIP, Amphi A<\/li>\n\n\n\n<li>Who: Ma\u00ebl Dumas (University of Warsaw)<\/li>\n\n\n\n<li>What: Variants of Merge-Width and Applications<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract:<\/strong><br>Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of several alternative definitions of merge-width, thus demonstrating the robustness of the notion. Our characterisation via definable merge-width uses vertex orderings inspired by generalised colouring numbers from sparsity theory, and enables us to obtain the first non-trivial approximation algorithm for merge-width, running in time n^O(1)\u00b72^n. Using these alternative definitions we also establish that graphs of bounded merge-width admit sparse quotients with bounded strong colouring numbers, are quasi-isometric to graphs of bounded expansion, and admit neighbourhood covers with constant overlap.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 19\/03\/2026 at 14:00<\/li>\n\n\n\n<li>Where: LIP, amphi A<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Graph Meetings : Ana Beatriz Da Silveira Martins : (Even hole, triangle)-free graphs revisited + Milica Maksimovi\u0107 : Rainbow connectivity Maker-Breaker games<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 05\/03\/2026 at 14:00<\/li>\n\n\n\n<li>Where: LIRIS, room TBA<\/li>\n\n\n\n<li>Who: Ana Beatriz Da Silveira Martins (MC2, LIP)<\/li>\n\n\n\n<li>What: (even hole, triangle)-free graphs revisited<br><br><strong>Abstract:<\/strong><br>We revisit a classical paper about (even hole, triangle)-free graphs&nbsp; [Conforti, Cornuejols, Kapoor and Vuskovic, Triangle-free graphs that are signable without even holes, Journal of Graph Theory, 34(3), 204&#8211;220, 2000].<br>In fact, the previous study describes a more general class, the so called triangle-free odd signable graphs, and we further generalise the class to the (theta, triangle, wac)-free graphs.<br>A theta is a graph made of three chordless ab-paths of length at least 2, vertex-disjoint apart from a and b, and such that the only edges are the edges of the paths. An wac is a graph W= (H, c, c&#8217;) induced by a hole H together with two adjacent vertices c and c&#8217; that both have at least three neighbours in H (the terminology wac this stands for Wheel with Adjacent Centres).<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Who: Milica Maksimovi\u0107 (Univ Novi Sad)<\/li>\n\n\n\n<li>What: Rainbow connectivity Maker-Breaker games<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Blair Sullivan : Graph Modification in Algorithmic Differentiation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 26\/02\/2026 at 14:00<\/li>\n\n\n\n<li>Where: LIP, Amphi A<\/li>\n\n\n\n<li>Who: Blair Sullivan (Invited professor at MC2, LIP)<\/li>\n\n\n\n<li>What: Graph Modification in Algorithmic Differentiation<br><br><strong>Abstract:<\/strong><br>In this talk, we&nbsp;present graph-theoretic formulations of&nbsp;two&nbsp;problems with wide application in algorithmic differentiation (AD): accumulating a Jacobian matrix while minimizing multiplications (Minimum Cost), and obtaining a minimum-size matrix-free Jacobian representation (Minimum Representation). Both problems can be naturally modeled as finding sequences of graph modifications (vertex eliminations) in a directed acyclic graph. We recently showed that both problems are NP-complete, resolving a long-standing open problem in AD. For Minimum Cost, we also show that&nbsp;a relatively straight-forward O*(2n) algorithm is essentially best possible under the Exponential Time Hypothesis.&nbsp;Our results are facilitated by several illustrative structural insights about sequences of vertex eliminations. We conclude with a discussion of open problems related to parameterized algorithms, approximations, and problem variants allowing edge eliminations. In addition to sharing our results, we hope to instigate more collaboration between graph algorithms researchers and the AD community. This talk is based on joint work with Matthias Bentert, Alex Crane, Pal Drange, and Yosuke Mizutani.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Martin Milani\u010d: Inverting Ramsey: awesome graph parameters<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 12\/02\/2026 at 14:00<\/li>\n\n\n\n<li>Where: LIP, Amphi A<\/li>\n\n\n\n<li>Who: Martin Milani\u010d (University of Primorska in Koper, Slovenia)<\/li>\n\n\n\n<li>What: Inverting Ramsey: awesome graph parameters<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract:<\/strong><br>We investigate connections between two lines of research related to independent sets and cliques in graphs. One of them studies independence variants of graph parameters such as treewidth or degeneracy. The second line deals with graph classes where some parameters are bounded by a function of the clique number. A famous example is given by the family of \u03c7-bounded graph classes, where the chromatic number is bounded by a function of the clique number.<br>A Ramsey-type argument implies that a graph parameter is bounded by a function of the clique number in any graph class in which the independence variant of the parameter is bounded by a constant. If the reverse implication also holds, we say that the parameter is awesome; otherwise, it is awful. We identify a number of awesome and awful graph parameters, derive some algorithmic applications of awesomeness, and propose a number of open problems related to these notions.<br>This is joint work with Kenny Be\u0161ter \u0160torgel (FI\u0160 Novo mesto and Primorska), Cl\u00e9ment Dallard (Fribourg), Vadim Lozin (Warwick), and Viktor Zamaraev (Liverpool).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Cl\u00e9ment Legrand-Duch\u00eane: Dirac\u2019s theorem and the geometry of perfect matchings<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 13\/11\/2025 at 14:30<\/li>\n\n\n\n<li>Where: M7, ENS de Lyon<\/li>\n\n\n\n<li>Who: Cl\u00e9ment Legrand-Duch\u00eane (University in Krak\u00f3w, Poland)<\/li>\n\n\n\n<li>What: Dirac\u2019s theorem and the geometry of perfect matchings<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Dirac&#8217;s theorem states that all n-vertex graphs with minimum degree n\/2 contain a perfect matching. This is tight and graphs with minimum degree cn are more generally called c-Dirac graphs. In fact, a phase transition occurs at c=1\/2: c-Dirac graphs with c \\ge 1\/2 contain (cn\/-e+o(1)))^{n\/2} perfect matchings [Cuckler, Kahn 2009]. Moreover, for any fixed c-Dirac graph G with c &gt;= 1\/2, there exist nice probability distributions on the perfect matchings of G called spread distributions [Pham, Sah, Sawhney, Simkin 2024]; as a result, if the edges of $G$ are sampled with probability O(\\log(n)\/n), the resulting graph still contains a perfect matching with good probability, thereby witnessing that these matchings are &#8220;everywhere&#8221; in G.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">With Ross Kang, we give a new understanding of this phase transition by describing how the perfect matchings of a Dirac graph cluster. More precisely, we analyse the geometrical properties of the space of perfect matchings of $G$, endowed with the graph metric such that perfect matchings differing on at most k edges are at distance one. For any fixed k, we pinpoint sharp thresholds at which this space is shattered into exponentially many components, has isolated perfect matchings, becomes connected, or becomes an expander.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Laure Morelle : H-Planarity and Parametric Extensions: when Modulators Act Globally<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 11\/12\/2025 at 14:30<\/li>\n\n\n\n<li>Where: Room M7 (3rd floor), LIP,  ENS de Lyon<\/li>\n\n\n\n<li>Who: Laure Morelle (University of Bergen)<\/li>\n\n\n\n<li>What: H-Planarity and Parametric Extensions: when Modulators Act Globally<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Abtract: <br>We introduce a series of graph decompositions based on the modulator\/target scheme of modification problems. As such, we define H-Planarity as the problem of deciding whether a graph G contains a vertex set X such that the torso of X is planar and the connected components of G-X are in H. We prove that, if H is hereditary, CMSO-definable, and decidable in polynomial time, then H-Planarity is solvable in polynomial time.<br>Additionally, we define two planar extensions of elimination distance to H and H-treewidth, namely H-planar treedepth and H-planar treewidth, for which we find FPT results under some mild conditions on H.<br>All previous (meta) algorithmic studies on modulators deal with modulators of \u201clow bidimensionality\u201d in the sense that they cannot be spread along a grid-minor of the input graph. Our results are the first to handle the situation where the modulators act globally. For this, we introduce a new version of the \u201cirrelevant vertex technique\u201d that can deal with modulators that may act \u201ceverywhere\u201d in the input graph.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Alexander Crane: Probabilistic Network Design<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 26\/09\/2025 at 14:00<\/li>\n\n\n\n<li>Where: Amphi A1, ENS de Lyon<\/li>\n\n\n\n<li>Who: Alexander Crane (University of Utah)<\/li>\n\n\n\n<li>What: Probabilistic Network Design<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Probabilistic graphs allow us to model randomized propagation<br>in graphs, for example communication in lossy networks or the spread of<br>information in a social network. In a realization of a probabilistic<br>graph G = (V, E, p), each edge in E is said to be &#8220;active&#8221;<br>independently with probability p. The proximity of a vertex pair u, v<br>is the probability with which there exists a uv-path consisting<br>entirely of active edges. The reach of G is the minimum proximity<br>across all vertex pairs.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In this talk, we will cover some recent approximation results on a<br>natural network design question in this setting: given a probabilistic<br>graph G and a budget k, how can we choose k edges to add to G such that<br>the reach of the resulting graph is maximized? The results rely on<br>connections to the k-center clustering problem, with an assist from<br>tools developed in percolation theory.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Alexey Gorelov: Lifting maps between graphs to embeddings<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 19\/06\/2025 at 10:30<\/li>\n\n\n\n<li>Where: Room B1, ENS de Lyon<\/li>\n\n\n\n<li>Who: Alexey Gorelov (Institut Fourier)<\/li>\n\n\n\n<li>What: Lifting maps between graphs to embeddings<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Let $f \\colon G \\to H$ be a graph homomorphism. In general, $f$ is not injective. The goal is to transform $f$ into an embedding by introducing a new dimension, that is, replacing $H$ by the space $<code>|H|<\/code> \\times \\mathbb{R}$, and perturbing $f$ along the new dimension. This task was originally motivated by similar problems in topology, which were in turn motivated by the classical embeddability question. Our problem can be reformulated in a purely combinatorial way. A \\emph{combinatorial lifting} of $f \\colon G \\to H$ is a collection of linear orders $&lt;_{v}$ on $f^{-1}(v)$ for all $v \\in V(H)$ such that no crossings occur. A crossing is a pair of edges $x_1 y_1, x_2 y_2 \\in E(G)$ with $f(x_1) = f(x_2) = v$, $f(y_1) = f(y_2) = w$, and $x_1 &gt;_v x_2$ while $y_1 &lt;_w y_2$. We study the computational complexity of deciding whether such a lifting exists. In a former work, we showed that this problem is NP-complete in general. However, for the special case of maps from trees to path graphs, we proved a complete criterion that can be checked in polynomial time. Our approach relies on combining and transforming liftings, a technique that may be of independent interest.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Graph meetings: Malory Marin &amp; Yannick Mogge<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When: 22\/05\/2025 at 14:00<\/li>\n\n\n\n<li>Where: LIRIS<\/li>\n\n\n\n<li>Who (1st speaker): Malory Marin (LIP)<\/li>\n\n\n\n<li>What: Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Given a graph G, the hard-core model defines a probability distribution over its independent sets, assigning to each set of size k a probability of \u03bb^k\/Z, where \u03bb&gt;0 is a parameter known as the fugacity and Z is a normalization constant. The Glauber dynamics is a simple Markov chain that converges to this distribution and enables efficient sampling. Its mixing time&#8211;the number of steps needed to approach the stationary distribution&#8211;has been widely studied across various graph classes, with most previous work emphasizing the dichotomy between polynomial and exponential mixing times, with a particular focus on sparse classes of graphs.<br>We investigate subexponential mixing times of the Glauber dynamics on geometric intersection graphs, such as disk graphs. We also study parameterized mixing times by focusing on two structural parameters that can remain small even in dense graphs: the tree independence number and the path independence number. We show that Glauber dynamics mixes in polynomial time on graphs with bounded path independence number and in quasi-polynomial time when the tree independence number is bounded. Moreover, we prove both bounds are tight, revealing a clear separation between the two parameters.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Who (2nd speaker): Yannick Mogge (LIRIS)<\/li>\n\n\n\n<li>What: Variants of Maker-Breaker games on complete and random graphs<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">In this talk we discuss two variants of Maker-Breaker games: fast strategies in Waiter-Client games, as well as a result for Connector-Breaker and Walker-Breaker games.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Waiter-Client games are played on some hypergraph $(X, \\mathcal{F})$, where $\\mathcal{F}$ denotes the family of winning sets. During each round of the game, Waiter offers two elements of $X$ to Client, from which she claims one for himself and the other element goes to Waiter. Waiter wins the game, if he can force Client to claim all the elements of a winning set from $\\mathcal{F}$.<br>We will discuss fast strategies for the Waiter-Client Hamiltonicity game on the edges of the complete graph $K_n$, and we will show that Waiter can force Client to claim a Hamilton cycle within $n+1$ rounds.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Connector-Breaker and Walker-Breaker games are defined similarly to Waiter-Client games on graphs, but in each round both players claim some predefined number of edges for themselves, with the additional restriction that Connector (or Walker) has to play in such a way that her graph stays connected throughout the game (or according to a walk). We will discuss the $(2:2)$-biased version of those games (where both players claim two edges of the graph in each turn) on a random graph $G \\sim G_{n,p}$ and we will show that the threshold probabilities for Connector\/Walker to claim a Hamilton cycle are of order $n^{-2\/3 + o(1)}$.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">See the <a href=\"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/GraphesALyon\" data-type=\"link\" data-id=\"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/GraphesALyon\">archives<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Graphes@Lyon is the graph theory seminar jointly organized by the MC2 team at LIP and the GOAL team at LIRIS. Local organizers: Nicolas Bousquet (LIRIS) and R\u00e9mi Watrigant (MC2). Contact us if you want to give a talk! Upcoming talks Linda Kleist (Univ. Hambourg) and Joseph Dorfer (TU Graz) Joseph Dorfer&nbsp; Title: Flip distance between &hellip; <a href=\"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/grapheslyon\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Graphes@Lyon&#8221;<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-145","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/pages\/145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/comments?post=145"}],"version-history":[{"count":29,"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/pages\/145\/revisions"}],"predecessor-version":[{"id":230,"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/pages\/145\/revisions\/230"}],"wp:attachment":[{"href":"https:\/\/www.ens-lyon.fr\/LIP\/MC2\/index.php\/wp-json\/wp\/v2\/media?parent=145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}