|
|||||
- ÉDOUARD BONNET, CNRS, ÉNS Lyon
Twin-width [PDF]
-
We will survey some combinatorial properties of the recently introduced classes of bounded twin-width.
- CHUN-HUNG LIU, Texas A&M University
Asymptotic dimension of minor-closed families and beyond [PDF]
-
We prove that the asymptotic dimension of any minor-closed families of graphs, any class of graphs of bounded tree-width, and any class of graphs with bounded layered tree-width are at most 2, 1 and 2, respectively. The first result solves a question of Fujiwara and Papasoglu; the second and third results solve a number of questions of Bonamy, Bousquet, Esperet, Groenland, Pirot and Scott. These results are optimal, improve a number of results in the literature, and imply known and new results about weak diameter coloring and clustered coloring on graphs.
- ROSE MCCARTY, University of Waterloo
Connectivity for adjacency matrices and vertex-minors [PDF]
-
Standard notions of graph connectivity do not translate well to its adjacency matrix (i.e. the complete bipartite graph is highly vertex- and edge-connected, but its adjacency matrix has rank $2$). The cut-rank function addresses this issue and is very closely related to vertex-minors. We will discuss the ``connectivity" issues that come up when forbidding a vertex-minor. Essentially, we characterize when the ``connectivity" of many disjoint sets can be decreased by adding a low-rank matrix (over the binary field). Joint work with Jim Geelen and Paul Wollan.
- RICHARD MONTGOMERY, University of Birmingham
A solution to Erdős and Hajnal's odd cycle problem [PDF]
-
I will discuss how to construct cycles of many different lengths in graphs, in particular answering the following two problems on odd and even cycles. Erdős and Hajnal asked in 1981 whether the sum of the reciprocals of the odd cycle lengths in a graph diverges as the chromatic number increases, while, in 1984, Erdős asked whether there is a constant C such that every graph with average degree at least C contains a cycle whose length is a power of 2.
This is joint work with Hong Liu.
- SOPHIE SPIRKL, University of Waterloo
Excluding a tree and a biclique [PDF]
-
The Gyarfas-Sumner conjecture states that for every tree $T$, there is a function $f$ such that graphs with no induced $T$ have chromatic number bounded by $f$ of their clique number. Hajnal and Rodl proved that if we replace "clique number" by "biclique number" (the largest $t$ such that the graph contains $K_{t,t}$ as a subgraph) then the conjecture holds.
Bonamy, Bousquet, Pilipczuk, Rzazewski, Thomasse and Walczak recently showed that in this setting, if $T$ is a path, $f$ is polynomial. I will talk about a result extending this to all trees.
Joint work with Alex Scott and Paul Seymour.