|
|||||
- VIDA DUJMOVIC, University of Ottawa
Product structure Theorem(s) [PDF]
-
Dujmović, Joret, Micek, Morin, Ueckerdt and Wood (2019) showed that
every planar graph is a subgraph of the strong product of a bounded
treewidth graph and a path. This introductory mini-symposium talk will introduce
this \emph{product structure theorem} and its generalizations.
- LOUIS ESPERET, Laboratoire G-SCOP (CNRS, Univ. Grenoble Alpes)
Planar graphs have bounded nonrepetitive chromatic number [PDF]
-
A colouring of a graph is "nonrepetitive" if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the second half. Using the planar graph product structure theorem, we show that planar graphs have nonrepetitive colourings with a bounded number of colours, thus solving a problem raised by Alon, Grytczuk, Haluszczak and Riordan in 2002. We also generalise this result to graphs excluding a fixed minor or topological minor.
This is joint work with V. Dujmović, G. Joret, B. Walczak, and D.R. Wood.
- GWENAËL JORET, Université Libre de Bruxelles
Sparse universal graphs for planarity [PDF]
-
This talk focuses on the following two problems:
(1) What is the minimum number of edges in a graph containing all $n$-vertex planar graphs as subgraphs? The best known bound is $O(n^{3/2})$, due to Babai, Chung, Erdös, Graham, and Spencer (1982).
(2) What is the minimum number of *vertices* in a graph containing all $n$-vertex planar graphs as *induced* subgraphs? Here Bonamy, Gavoille, and Pilipczuk (2019) recently established a $O(n^{4/3})$ bound.
We show that a bound of $n^{1+o(1)}$ can be achieved for these two problems. Joint work with Vida Dujmović, Louis Esperet, Cyril Gavoille, Piotr Micek, and Pat Morin.
- PIOTR MICEK, Jagiellonian University
Centered colorings and vertex rankings [PDF]
-
A vertex coloring $\phi$ of a graph $G$ is $p$-centered
if for every connected subgraph $H$ of $G$
either $\phi$ uses more than $p$ colors on $H$ or there is a color
that appears exactly once on $H$.
A vertex coloring $\phi$ of a graph $G$ is an $\ell$-ranking of $G$ if for every connected subgraph $H$ of $G$ of diameter at most $\ell$ there is exactly one vertex of maximum color used by $\phi$ on $H$.
We are going to use the product structure theorem to deliver the best-known bounds on these parameters for planar graphs.
- DAVID WOOD, Monash University
Planar graphs have bounded queue-number [PDF]
-
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al.\ from 1992. The key to the proof is the following result: every planar graph is a subgraph of the strong product of some treewidth 8 graph and some path. We generalise the first result to show that every proper minor-closed class has bounded queue-number. This is joint work with Vida Dujmovi\'c, Gwena\"el Joret, Piotr Micek, Pat Morin and Torsten Ueckerdt [J. ACM 67.4:22, 2020].