Lyon graph meetings

The graph meetings aim at gathering people interested in graphs in the Lyon area.

We have physical meetings regularly, alternating between LIP (ENS Lyon) and LIRIS (University of Lyon). The usual format is: two 40 minute talks, on the board, with a lot of interaction.

Useful information

Announcements: The meetings are announced on the mailing list graphesalyon[at]liris.cnrs.fr
To join the list, write to Nicolas Bousquet (nicolas.bousquet[at]univ-lyon1.fr).

Contact: For any question about the meetings, contact Laurent: laurent.feuilloley[at]univ-lyon1.fr, and for urgent matter: 06 72 31 57 **, where ** is 34.

Places:

The LIP is at 46 Allée d'Italie, Lyon (Google maps, Open street map). The specific room varies. You might need to register at the entrance.
The LIRIS is in the Nautibus building in the La Doua Campus, 25 avenue Pierre de Coubertin in Villeurbanne (static map, Google maps, Open street map). We usually use one of the following two rooms: the "salle visio", directly on the left when entering the building, and the room of the second floor, on the right when using the stairs (for this one, you might need a local to open the door).

Schedule

A tentative schedule for the meetings of Autummn 2024: TBA.

→ Next meeting: September 19

The meeting will take place on Thursday September 19, at 10AM at LIRIS, room TD 116 (1st floor).
Menu:
- What ordered patterns tell us about induced paths, by Julien Duron
- A recoloring version of a conjecture of Reed, by Lucas de Meyer.

Past meetings

Academic year 2023-2024

25th graph meeting - June 20 2024

The meeting took place on Thursday June 20, at 9:30AM, at LIP, in M7.315.
Menu:
- Linear time algorithms for pattern detection in ordered graphs: the chordal case, by François Pitois.
  Links: the paper.
- Local certification of geometric graph classes, by Jean-Florent Raymond.
  Links: the paper.

24th graph meeting - May 23 2024

The meeting took place on Thursday May 23, at 10AM, at LIP, in Salle du conseil.
Menu:
- Reconfstruction, by Théo Pierron.
  Links: an earlier paper on the topic.
- Factoring Pattern-Free Permutations into Separable ones, by Colin Geniet.
  Links: the paper.

23rd graph meeting - April 18 2024

The meeting took place on Thursday April, at 10 AM, at the LIRIS, in room C1.
Menu:
- Partition strategies for the Maker-Breaker domination game, by Aline Parreau.
  Links: the paper introducing the game.
- Grounded intersection graphs and forbidden ordered subgraphs, by Laurent Feuilloley.
  Links: the paper.

22nd graph meeting - March 14 2024

The meeting took place on Thursday March 14, at 10 AM, at the LIRIS, in room 008 (former C5). Théo Pierron chaired.
Menu:
- Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes, by Édouard Bonnet.
  Links: the paper.
- Short and local transformations between (Δ+1)-colorings, by Nicolas Bousquet
  (thanks Nicolas for replacing me at the last minute!).
  Links: the paper.

21st graph meeting - December 7 2023

The meeting took place on Thursday December 7, at 2:15 PM, at the LIRIS, in room C1.
Menu:
- Dualization of bounded VC-dimension hypergraphs, by Arnaud Mary.
- Detection of induced minors, by Nicolas Trotignon and Clément Dallard.

20th graph meeting - November 9 2023

The meeting took place on Thursday November 9, at 2 PM, at the LIRIS, at the second floor (chaired by Théo).
Menu:
- Fast winning strategies for the attacker in eternal domination, by Nacim Oijid.
- Kernelizing Temporal Exploration Problems, by Emmanuel Arrighi.
  Links: the paper.

19th graph meeting - October 19 2023

The meeting took place on Thursday October 19, at 2:15 PM, at the LIP, in salle du conseil.
Menu:
- Global certification, bipartiteness, and hashing, by Sébastien Zeitoun
- Lower bound on the density of 4-critical planar graph, by Carl Feghali.
  Links: the paper.

18th graph meeting - September 21 2023

The meeting took place on Thursday September 21, at 2PM, at the LIP, in salle M7.
Menu:
- Parity matroid reconfiguration, by Nicolas Bousquet
- A tamed family of triangle-free graphs with unbounded chromatic number, by Colin Geniet.
  Links: the paper.

Academic year 2022-2023

17th graph meeting - July 11 2023

The meeting took place on Tuesday July 11, at 10AM, at the LIP, in salle du conseil.
Menu:
- Dynamic Graph Colouring, by Juliette Vlieghe.
  Links: the master thesis.
- Stretch-width, by Julien Duron.
  Links: the paper.

16th graph meeting - June 27 2023

The meeting took place on Tuesday June 27, at 10AM, at the LIP, in Room B1.
Menu:
- The Cops and Robber Game on Surfaces, by Alexandra Wesolek.
  Links: The two relevant papers: here and there.
- Well-covered partition and beyond, by Malory Marin.
  Links: a related paper.

15th graph meeting - June 8 2023

The meeting took place on Thursday June 8, at 3PM, at the LIRIS, in Salle de TD10.
Menu:
- Isometric Path complexity of graphs, by Dibyayan Chakraborty.
- Distance-2 coloring in planar graphs, by Quentin Deschamps.
  Links: the paper , and a related paper.

14th graph meeting - May 5 2023

The meeting took place on Friday May 5, at 10AM, at the LIRIS, in Salle de TD1.
Menu:
- Graph parameters in low-dimensional topology, by Kristóf Huszár.
  Links: the most recent paper on the topic.
- When Should You Wait Before Updating?, by Laurent Feuilloley.
  Links: the paper.

13th graph meeting - April 4 2023

The meeting took place on Tuesday April 4th, at 2PM, at the LIP, in Salle du conseil LIP, 394 nord.
Menu:
- Pattern detection in ordered graphs, by François Pitois.
  Links: the paper.
- Finding large tree structures in digraphs, by Stéphan Thomassé.
  Links: the paper that introduced the problem (but not the solution).

12th graph meeting - January 17 2023

The meeting took place on Tuesday January 17th, at 10AM, at the LIRIS, in Salle visio.
Menu:
- Partizan subtraction games, by Éric Duchêne.
  Links: the paper.
- Ordering and geometric restrictions does not imply easy recognition, by Dibyayan Chakraborty.
  Links: related paper.

11th graph meeting - December 13 2022

The meeting took place on Tuesday December 13, at 10AM, at the LIRIS, in Salle visio. This meeting had a very low attendance, hence the speakers will give their talks again later this year.
Menu:
- Wi-Fi channel allocation revisited, by Rémi Watrigant.
- Highly connected $K_{2,t}$-minor-free graphs do not exist, by Théo Pierron.
  Links: The paper.

10th graph meeting - November 22 2022

The meeting took place on Tuesday November 22, at 2PM, at the LIP, in Salle de conseil.
Menu:
- Graphs with every hole of length 2023, by Nicolas Trotignon.
  Links: the paper.
- Introduction to distributed graph coloring, by Laurent Feuilloley.
  Links: a blog post with distributed graph algorithm material and a book about distributed graph coloring.

Academic year 2021-2022

9th graph meeting - June 16th 2022

The meeting took place on on Thursday June 16th, at 10AM, at the LIRIS, in room C1.
Menu:
- Incidence, a scoring positional game, by Nacim Oijid.
  Links: the paper.
- Graphs without independent cycles, by Stéphan Thomassé.
  Links: the newest paper on the topic.

8th graph meeting - June 3rd 2022

The meeting took place on Friday June 3rd, at 2PM, at the LIP, in room B1.
Menu:
- Independent set reconfiguration meets arithmetic progressions, by Nicolas Bousquet.
  Links: The paper, the webpage of the CORE challenge, a relevant wikipedia article about arithmetic-progression-free sets.
- Twin-width can be exponential in treewidth, by Hugues Déprés.
  Links: the paper.

Seventh graph meeting - May 19th 2022

The meeting took place at LIRIS, in the room of the second floor, at 10 AM.
Schedule:
- Open problems on geodetic sets and cluster vertex deletion, by Dibyayan Chakraborty.
  Links: a paper about geodesic sets, and one about Cluster Vertex Deletion.
- The Maker-Breaker domination game on graphs, by Aline Parreau.
  Links: the paper that introduced the game.

Sixth graph meeting - December 9th 2021

The meeting took place at LIRIS, in Salle visio at 2 PM.
Schedule:
- Graph modification problems, by Nicolas Bousquet.
  Links: a survey about edge modification problems, the paper with the sublinear kernel , and the PACE challenge website.
- Twin-width of bounded degree graphs and groups, by Colin Geniet.
  Links: the paper about twinwidth and small classes.

Fifth graph meeting - November 26th 2021

The meeting took place at ENS, at the "Salle du conseil" at 10:30 AM.
Schedule:
- Median and simplex graphs, by Pierre Bergé.
  Links: Median graphs on wikipedia. Two recent papers about the diameter of median graphs: here and there.
- Model checking for first-order logic with connectivity predicate, by Alexandre Vigny.
  Links: The two papers: here and there.

Forth graph meeting - November 4th 2021

The meeting took place at LIRIS, in the "Salle visio" at 2PM.
Schedule:
- About Courcelle's theorem and metric dimension, by Quentin Deschamps.
  Links: Courcelle's theorem and metric dimension on wikipedia.
- Introduction to graph burning, by Théo Pierron.
  Links: The paper introducing graph burning, the new preprint with 4/3 ratio, and the survey about the firefighter problem.

Third graph meeting - October 14th 2021

The meeting took place at 2PM at the LIP, room 7.
Schedule:
- A new proof of Courcelle's theorem with contraction sequences, by Édouard Bonnet.
  Links: Courcelle's theorem on wikipedia, the paper with the new proof.
- Open problem about connectivity of a random graph family, by Bora Ucar.

Second graph meeting - October 1st 2021

The meeting took place at LIRIS, in the "Salle visio" (ground level, on the left of the entrance) at 10:30.
Schedule:
- 30-minute talk about Burling graphs, by Pegah Pournajafi.
  Links: The two papers on the topic by Pegah here and there.
- Mini-talk about diagonal rectangle graphs, by Laurent Feuilloley.
  Links: Paper about forbidden patterns and a recent paper about diagonal rectangle graphs.

First graph meeting - September 20th 2021

The meeting took place at LIP in the Salle du conseil. (Meeting at the coffee corner "coin café" at 10:30.)
Schedule:
- Introduction, announcements,
- Mini-talk about a graphclasses.org update by Nicolas Trotignon.
  Link: the graphclasses website.
- Mini-talk about recoloring by Carl Feghali.
  Link: a recent paper on recoloring by Carl.
- Mini-talk about metric dimension by Quentin Deschamps.
  Link: Metric dimension on wikipedia.