Sparse Graphs Coalition

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== 2023 Session 1 : χ-boundedness =====

The goal is to share recent developments in the area of χ-boundedness, a topic that has progressed nicely in recent years. We will also form problem-solving groups to work on open questions in the area.

The workshop is intended to last one week, starting with one talk, an open problem session, and the formation of independent working groups on the Monday. Each group determines its own working pattern/schedule during the week. On each of the following days, the participants meet altogether briefly to share progress and perhaps follow a talk.

==== Organisers ====

[[https://www.trinhall.cam.ac.uk/contact-us/contact-directory/fellows-and-academics-directory/james-davies/|James Davies]], [[https://staff.fnwi.uva.nl/j.r.kang/|Ross Kang]], [[https://www.tcs.uj.edu.pl/walczak|Bartosz Walczak]]


==== Workshop dates ====

27-31 March 2023

==== Registration ====

Participants can register fully (talks + working groups) or attend only the talks.
To maximise interaction and intimacy the full participation capacity is limited.
We may need to restrict based on ensuring balance in experience and diversity in the groups.

[[https://forms.gle/EkshbnGH8bmT5XfY6|Application for full participation]] (closed)

Deadline for application: 17 March 2023 (closed)

The zoom link for talks will be published here by the start of the workshop.

==== Confirmed participants ====

  * [[https://www.trinhall.cam.ac.uk/contact-us/contact-directory/fellows-and-academics-directory/james-davies/|James Davies]] (organiser)
  * [[https://staff.fnwi.uva.nl/j.r.kang/|Ross Kang]] (organiser)
  * [[https://www.tcs.uj.edu.pl/walczak|Bartosz Walczak]] (organiser)
  * Sophie Spirkl*
  * Marcin Briański
  * Lech Duraj
  * Piotr Micek
  * Hoang La
  * Alex Scott*
  * Dan Cranston
  * Amadeus Reinald
  * Lena Yuditsky
  * Antonio Girao
  * Zdeněk Dvořák
  * Maximilian Gorsky
  * Jean-Sébastien Sereni
  * Linda Cook
  * Rimma Hamalainen
  * Seokbeom Kim
  * Robert Hickingbotham
  * Hudson LaFayette
  * Grzegorz Guśpiel
  * Patrice Ossona de Mendez
  * Jonathan Narboni
  * Clément Rambaud
  * Chaya Keller
  * Jan Volec
  * Maximilian Wötzel
  * Maria Chudnovsky
  * Rose McCarty
  * Paweł Rzążewski
  * Stijn Cambie
  * David Mikšaník
  * Raphael Steiner
  * Filip Pokrývka
  * František Kardoš
  * Michał Seweryn
  * Micha Christoph
  * Paloma T. Lima
  * Tomas Kaiser
  * Sepehr Hajebi
  * Hidde Koerts
  * Aristotelis Chaniotis
  * Paul Seymour

* indicates speaker
   
==== Open problems ====

A major aim is, in small groups, to work on and make progress on open problems related to the themes of the workshop. Such problems are warmly welcomed by email to the organisers. These will be shared to full participants a few days before the start of the workshop. You may be asked to prepare a 5 to 10 minute presentation of your problem on the Monday.

Please use the following template for submissions:

Template: {{ sessions:2022sessions:opl-example.tgz| download}}

Deadline: 21 March 2023 (closed)

==== Schedule (all times Central European Summer Time) ====

We prioritise European participation, but to allow more possibilities for participation from different timezones as well as to keep the workshop lightweight, we limit most plenary activities to between 14:00 and 17:00.

1. //Monday, 27 March//
  * 14:05 welcome
  * 14:15 open problem session
  * 15:45 group formation
2. //Tuesday 28 March//
  * 14:05 talk
  * 15:05 break
  * 15:15 group updates
3. //Wednesday 29 March//
  * 15:15 group updates
  * 16:15 talk
4. //Thursday 30 March//
  * 15:15 group updates
5. //Friday, 31 March//
  * 15:15 final updates
  * 16:30 close of meeting 

==== Talks (all times Central European Summer Time) ====

=== Sophie Spirkl: χ-boundedness and η-boundedness ===

I will talk about η(G), the minimum size of a set of vertices X in G such that α(G\X) < α(G). This parameter has some surprising parallels with χ(G), and in particular, one can ask about “η-boundedness,” defined analogously to χ-boundedness. I will present some results and open questions about this.

This is based on joint work with Sepehr Hajebi and Yanjia Li.

14:05, 28 March, https://uva-live.zoom.us/j/81672886664

=== Alex Scott: On a problem of El-Zahar and Erdős ===

Two subgraphs A, B of a graph G are anticomplete if they are vertex-disjoint and there are no edges joining them. Is it true that if G is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by El-Zahar and Erdős in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results.

We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number. Second, we look at what happens if we replace the hypothesis that G has large chromatic number with the hypothesis that G has sufficiently large minimum degree. This, together with excluding K_t, is not enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of excluding a complete graph we exclude a complete bipartite graph. Finally, we discuss analogous problems for tournaments.

This is joint work with Tung Nguyen and Paul Seymour.

16:15, 29 March, https://us06web.zoom.us/j/88229832543?pwd=bmJidUVEcDJwaGZnTVJQNnFGTGdZQT09 (co-hosted by Jagiellonian TCS seminar)

==== Research results ====

  * Duraj, Kang, La, Narboni, Pokrývka, Rambaud, Reinald. The χ-binding function for d-directional segment graphs. https://arxiv.org/abs/2309.06072