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 until the end of 2023.

Thursday December 7, afternoon, at LIP?
Thursday December 21, afternoon (to be confirmed).

→ Next meeting: December 7

The meeting will take place on Thursday December 7, at 2:15 PM at LIP. Room TBA.
Menu:
- Dualization of bounded VC-dimension hypergraphs, by Arnaud Mary.
- Detection of induced minors, by Nicolas Trotignon and Clément Dallard.

Past meetings

20th graph meeting - November 9

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.