# Schedule for: 21w5513 - New Perspectives in Colouring and Structure (Online)

Beginning on Monday, October 18 and ending Saturday October 23, 2021

All times in UBC Okanagan, Canada time, PDT (UTC-7).

Monday, October 18 | |
---|---|

09:20 - 09:30 | Introduction by BIRS (Zoom2) |

09:30 - 10:20 |
Stéphan Thomassé: Classes of graphs with bounded and unbounded twin-width ↓ We will briefly review the main properties of graphs and matrices with
bounded twin-width, and then focus on two topics:
(Zoom2) i) How to construct classes of graphs with unbounded twin-width which are small (growth $c^n.n!$). Can we make this construction explicit? ii) Does forbidding induced subdivisions of cubic graphs lead to bounded twin-width in the sparse case? Proof for some particular cases. The main challenge behind is of course to find some weak dual to twin-width certifying that a class has indeed unbounded twin-width. Joint work with: E. Bonnet, C. Geniet, U. Giocanti, E.J. Kim, P. Ossona de Mendez, A. Reinald, P. Simon, Szymon Torunczyk, R. Watrigant. |

10:20 - 10:30 | Group photo (Zoom2) |

10:30 - 11:00 |
Zdenek Dvorak: Progress on number of 3-colorings of triangle-free planar graphs ↓ Thomassen recently disproved his conjecture that triangle-free planar graphs
have exponentially many colorings. We present an improved upper bound and give
a supporting evidence towards the conjecture that it could be tight.
Joint work with Luke Postle. (Zoom2) |

11:10 - 12:00 |
Sergey Norin: The extremal function of minor-closed graph classes ↓ For a graph class $F$, let $ex_{F}(n)$ denote the maximum number of edges in an $n$-vertex graph in $F$.
Jointly with Rohan Kapapia, we've proved that $ex_{F}(n)$ is a sum of a linear function and an eventually periodic function for every proper
minor-closed graph class $F$.
We will discuss the proof and consequences of this theorem and related open
questions. (Zoom2) |

Tuesday, October 19 | |
---|---|

09:30 - 10:20 |
Luke Postle: Reducing linear Hadwiger's conjecture to coloring small graphs ↓ In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t ≥ 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t (\log t)^{0.5})$ and hence is $O(t (\log t)^{0.5})$-colorable. In a recent breakthrough, Norin, Song, and I proved that every graph with no $K_t$ minor is $O(t \log t)^c)$-colorable for every $c > 0.25$. Subsequently I showed that every graph with no $K_t$ minor is $O(t (\log\log t)^6)$-colorable.
(Zoom2) We improve upon this further by showing that every graph with no $K_t$ minor is $O(t \log \log t)$-colorable. Our main technical result yields this as well as a number of other interesting corollaries. A natural weakening of Hadwiger's Conjecture is the so-called Linear Hadwiger's Conjecture that every graph with no $K_t$ minor is $O(t)$-colorable. We prove that Linear Hadwiger's Conjecture reduces to small graphs. In 2003, Kühn and Osthus proved that Hadwiger’s Conjecture holds for graphs of girth at least five (provided that t is sufficiently large). In 2005, Kühn and Osthus extended this result to the class of $K_{s,s}$-free graphs for any fixed positive integer $s ≥ 2$. Along this line, we show that Linear Hadwiger's Conjecture holds for the class of $K_r$-free graphs for every fixed $r$. This is joint work with Michelle Delcourt. |

10:30 - 11:00 |
Marthe Bonamy: Exploring the space of colourings with Kempe changes ↓ Kempe changes were introduced in 1879 in an attempt to prove the
4-colour theorem. They are a convenient if not crucial tool to prove various
colouring theorems. Here, we consider how to navigate from a colouring to
another through Kempe changes. When is it possible? How fast? (Zoom2) |

11:10 - 12:00 |
Jacob Fox: The structure of triangle-free graphs ↓ I plan to survey a variety of problems and results on the structure of triangle-free graphs and extensions, discussing their relationship to major topics like Hadwiger’s conjecture,
the graph removal lemma,
the Erdős-Hajnal conjecture, Turán's theorem, and Ramsey goodness. (Zoom2) |

Wednesday, October 20 | |
---|---|

16:00 - 16:50 |
Chun-Hung Liu: Weak diameter coloring of minor-closed families in large scale ↓ A weak diameter coloring of a graph $G$ is a coloring of the vertices such
that every monochromatic component has bounded diameter, where the
diameter is computed in $G$. In this talk we consider the smallest number
$c$ such that the $r$-th power of any graph in a fixed graph class has a
weak diameter coloring with $c$ colors for arbitrarily large $r$. This $c$ is
equivalent to the asymptotic dimension of metric spaces. We will
determine the smallest $c$ for every minor-closed family of graphs and for
every graph class with bounded layered treewidth. Simple corollaries of
these results solve some problems about Riemannian surfaces and
geometric group theory and rediscover known results about clustered
coloring of those classes with bounded maximum degree. Joint work with
Bonamy, Bousquet, Esperet, Groenland, Pirot and Scott. (Zoom2) |

17:00 - 17:50 |
David Wood: Universality for minor-closed classes with applications to graph colouring ↓ Stanislaw Ulam asked whether there exists a universal countable
planar graph (that is, a countable planar graph that contains every countable
planar graph as a subgraph). János Pach (1981) answered this question in the
negative. We strengthen this result by showing that every countable graph that
contains all countable planar graphs must contain (i) an infinite complete graph
as a minor, and (ii) arbitrarily large complete graph subdivisions. $$ $$
On the other hand, we construct a countable graph that contains all countable
planar graphs and has several key properties such as linear colouring numbers,
linear expansion, and every finite $n$-vertex subgraph has $O(\sqrt{n})$ treewidth
(which implies the Lipton-Tarjan separator theorem). The graph is the strong
product of the universal treewidth-6 graph and a 1-way infinite path. The proof
builds on the finite case due to Dujmović et al (2020), which has been the key
tool in the solution of several open problems. More generally, for every fixed
positive integer $t$ we construct a countable graph that contains every countable
$K_t$-minor-free graph and has the above key properties. $$ $$
Our final contribution is a construction, based on chordal partitions, of a
countable graph that contains every countable $K_t$-minor-free graph as an induced
subgraph, has linear colouring numbers and linear expansion, and contains no
subdivision of the countably infinite complete graph (implying (ii) is best
possible). $$ $$
Joint work with Tony Huynh, Bojan Mohar, Robert Šámal and Carsten Thomassen
[https://arxiv.org/abs/2109.00327]. (Zoom2) |

18:00 - 18:50 |
Ken-ichi Kawarabayashi: Low diameter decomposition, polylogarithmic approximation for directed sparsest-cut, and embedding into directed $\ell_1$ for directed planar graph ↓ The multi-commodity flow-cut gap is a fundamental parameter that affects
the performance of several divide & conquer algorithms, and has been
extensively studied for various classes of undirected graphs.
It has been shown by Linial, London and Rabinovich and by Aumann and
Rabani that for general $n$-vertex graphs it is bounded by $O(\log n)$
and the Gupta-Newman-Rabinovich-Sinclair conjecture asserts that it is
$O(1)$ for any family of graphs that excludes some fixed minor.
(Zoom2) We show that the multicommodity flow-cut gap on DIRECTED planar graphs is $O(\log^3 n)$. This is the first sub-polynomial bound for any (nontrivial) family of directed graphs. We remark that for general directed graphs, it has been shown by Chuzhoy and Khanna that the gap is $\Omega(n^{1/7})$, even for directed acyclic graphs. As a direct consequence of our result, we also obtain the first polynomial-time polylogarithmic-approximation algorithms for the Directed Non-Bipartite Sparsest-Cut, and the Directed Multicut problems for directed planar graphs, which extends the long-standing result for undirectd planar graphs by Rao in 1999 (with a slightly weaker bound). At the heart of our result we construct low diameter partitions of directed planar graphs, which is a purely graph theoretical result. We also investigate low-distortion quasimetric embeddings into directed $\ell_1$. Joint work with Tasos Sidiropoulos. |

Thursday, October 21 | |
---|---|

09:30 - 10:10 |
Louis Esperet: Local certification of graphs ↓ The talk will be a brief introduction to the field of local certification,
which is a nice bridge between structural graph theory and distributed
complexity theory.
(Zoom2) In local certification, the goal is to allow the vertices of a graph to decide "locally" if they belong to some fixed class $F$. Each vertex is given a small certificate, and after collecting the certificates of its neighbors each vertex decides if the graph lies in $F$. If the graph is indeed in $F$, all vertices must accept the instance, while if the graph is not in $F$, at least one vertex has to reject the instance. The goal is to minimize the size of the certificates. I will give a short proof that $n$-vertex planar graphs (and more generally graphs embeddable in a fixed surface) can be locally certified with $O(\log n)$ bits per vertex. The main open problem in the area is whether this extends to any proper minor-closed class. Joint work with Benjamin Lévêque. |

10:20 - 11:00 |
Bartosz Walczak: Coloring ordered graphs with excluded induced ordered subgraphs ↓ An ordered graph is a graph equipped with a total order on the vertices; two
edges of an ordered graph are crossing if their endpoints alternate in the
order. Various cases of graphs with geometric representations motivate the
following question: for which ordered graphs $H$ is the class of graphs excluding
$H$ as an induced ordered subgraph $\chi$-bounded? We provide complete answers for
connected ordered graphs $H$, for crossing-free ordered graphs $H$, and for all
4-vertex ordered graphs $H$. In particular, making use of a new construction of
triangle-free high-chromatic graphs, we show that ordered stars are the only
connected ordered graphs $H$ for which the class is $\chi$-bounded. (Joint work with
Piotr Mikołajczyk.) We also survey other known results on $\chi$-boundedness of
ordered graphs with excluded ordered patterns. (Zoom2) |

11:10 - 12:00 |
Nicolas Trotignon: Burling graphs revisited ↓ The Burling sequence is a sequence of triangle-free graphs of
increasing chromatic number. Any graph which is an induced subgraph of
a graph in this sequence is called a Burling graph. These graphs have
attracted some attention because they have geometric representations
and because they provide counter-examples to several conjectures about
bounding the chromatic number in classes of graphs.
(Zoom2) The goal of this talk is to provide new definitions of Burling graphs. Three of them are geometrical: they characterize Burling graphs as intersection graphs of various geometrical objects (line segments of the place, frame of the plane, axis-aligned boxes of $\mathbb{R}^3$). All these representations of Burling graphs were known. Our contribution is to add restrictions to the configurations of the geometrical objects so that there is an equivalence between the intersection graphs and the Burling graphs. Among our new equivalent definitions of Burling graphs, one is of a more combinatorial flavour. It says how any Burling graph can be derived from a tree with some specific rules. This definition is convenient decide whether some given graph is Burling or not. We use it to give several generic examples of Burling graphs or rules to find edges whose subdivision preserves being a Burling graph. We also use it to find examples of graphs that are not Burling. Among several consequences of all this, one is that graphs that do not contain any subdivision of $K_5$ as an induced subgraph have unbounded chromatic number. This is a joint work with Pegah Pournajafi. |

Friday, October 22 | |
---|---|

09:30 - 10:20 |
Maria Chudnovsky: Induced subgraphs and tree decompositions ↓ 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.
(Zoom2) 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. In what follows we mostly focus on families of graphs of bounded degree. It turns out that due to the bound on the degree, these collections of natural separations can be partitioned into a bounded number of laminar collections. This in turn allows to us obtain a wide variety of structural and algorithmic results, which we will survey in this talk. |

10:30 - 11:00 |
Sophie Spirkl: Logarithmic treewidth ↓ I will talk about a recent proof that graphs excluding a fixed
complete graph and a slightly extended set of three-path-configurations have
treewidth logarithmic in their number of vertices. This proves a conjecture of
Sintiari and Trotignon about (theta, triangle)-free graphs.
Joint work with Tara Abrishami, Maria Chudnovsky, and Sepehr Hajebi. (Zoom2) |

11:10 - 12:00 |
Marcin Pilipczuk: The Gyárfás' path argument and quasi-polynomial time algorithms in P_t-free graphs ↓ Graph classes excluding a path or a subdivided claw as an induced subgraph are
so far quite mysterious: on one hand, beside some corner cases, they do not seem
to have any good structural description, but on the other hand, a number of
combinatorial problems - including Maximum Independent Set (MIS) - lack an
NP-hardness proof in these graph classes, indicating a possible hidden structure
that can be used algorithmically. Furthermore, graphs excluding a fixed path as
an induced subgraph were one of the earliest examples of a chi-bounded graph
class, with an elegant proof technique dubbed the Gyárfás' path argument. In
recent years the progress accelerated, leading to, among other results, (a) a
quasi-polynomial time algorithm for MIS in
graphs excluding a fixed path as an induced subgraph, (b) a QPTAS for MIS in
graphs excluding a subdivided claw as an induced subgraph, (c) the proof of the
Erdős-Hajnal property in graph classes excluding a fixed forest and its
complement. In the talk, after a quick survey of these results, I will focus on
the most recent developments - the quasi-polynomial time algorithms for MIS and
related problems in P_t-free graphs. (Zoom2) |

12:10 - 13:00 |
Paweł Rzążewski: Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws ↓ For graphs $G$ and $H$, we say that $G$ is $H$-free if it does not
contain $H$ as an induced subgraph. Already in the early 1980s Alekseev
observed that if $H$ is connected, then the Max Weight Independent Set
problem (MWIS) remains NP-hard in $H$-free graphs, unless $H$ is a path or a
subdivided claw, i.e., a graph obtained from the three-leaf star by
subdividing each edge some number of times (possibly zero). Since then
determining the complexity of MWIS in these remaining cases is one of
the most important problems in algorithmic graph theory.
(Zoom2) A general belief is that the problem is polynomial-time solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. More conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in $H$-free graphs, where $H$ is any fixed path. If $H$ is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponential-time algorithm [Chudnovsky et al., SODA 2019]. We make an important step towards solving the problem by showing that for any subdivided claw $H$, MWIS is polynomial-time solvable in $H$-free graphs of bounded degree. The results are joint work with T. Abrishami, M. Chudnovsky, and C. Dibek. |