# Schedule for: 17w5154 - Geometric and Structural Graph Theory

Beginning on Sunday, August 20 and ending Friday August 25, 2017

All times in Banff, Alberta time, MDT (UTC-6).

Sunday, August 20 | |
---|---|

16:00 - 17:30 | Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk - Professional Development Centre) |

17:30 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

20:00 - 22:00 | Informal gathering (Corbett Hall Lounge (CH 2110)) |

Monday, August 21 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

08:45 - 09:00 | Introduction and Welcome by BIRS Station Manager (TCPL 201) |

09:00 - 10:00 |
David Wood: Tutorial on defective and clustered graph colouring ↓ Consider the following two ways to colour a graph where the
requirement that adjacent vertices get distinct colours is relaxed. A
colouring has DEFECT $d$ if each monochromatic component has
maximum degree at most $d$. A colouring has CLUSTERING $c$ if
each monochromatic component has at most $c$ vertices. This talk
surveys recent progress on these types of colourings for the following
graph classes: planar graphs, graphs embeddable in surfaces, graphs
with given maximum degree, graphs with linear crossing number,
linklessly or knotlessly embeddable graphs, graphs with given Colin de
Verdiere parameter, graphs with given thickness, graphs with given
book-thickness, graphs excluding $K_t$ as a minor, graphs excluding
$K_{s,t}$ as a minor, and graphs excluding an arbitrary graph $H$ as a
minor. Several open problems are discussed. This is joint work with
Patrice Ossona de Mendez and Sang-il Oum (arXiv:1611.09060), Bojan
Mohar and Bruce Reed (arXiv:1612.05674), Jan van den Heuvel
(arXiv:1704.06536), and Sergey Norin, Alex Scott and Paul Seymour
(arXiv:1708.02370). (TCPL 201) |

10:00 - 10:20 | Coffee Break (TCPL Foyer) |

10:20 - 11:20 |
Sergey Norin: Tutorial on defective colouring continued ↓ We continue the survey of defective and clustered colorings of minor-closed
classes of graphs of graphs, focusing on the techniques and conjectures. The
discussed techniques include: islands, separators, decompositons of graphs
in minor closed classes into graphs of bounded treewidth, and linear
decompositions of graphs of bounded treewidth. Based on joint work with
Dvorak, and with Scott, Seymour and Wood. (TCPL 201) |

11:30 - 13:30 |
Eclipse and lunch ↓ Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

14:20 - 14:30 |
Group Photo ↓ Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo! (TCPL Foyer) |

14:30 - 15:30 |
Zixia Song: Coloring graphs with forbidden minors ↓ As pointed out by Seymour in his recent survey on Hadwiger's conjecture,
proving that graphs with no \(K_7\) minor are 6-colorable is the first
case of Hadwiger's conjecture that is still open. It is not known yet
whether graphs with no \(K_7\) minor are 7-colorable. Using a Kempe-chain
argument along with the fact that an induced path on three vertices is
dominating in a graph with independence number two, we first give a very
short and computer-free proof of a recent result of Albar and Goncalves,
and generalize it to the next step by showing that every graph with no
\(K_t\) minor is \((2t-6)\)-colorable, where \(t\in\{7,8,9\}\). We then prove
that graphs with no \(K_8^-\) minor are 9-colorable, and graphs with no
\(K_8^=\) minor are 8-colorable. Finally we prove that if Mader's bound
for the extremal function for \(K_t\) minors is true, then every graph with
no \(K_t\) minor is \((2t-6)\)-colorable for all \(t\ge6\). This implies our
first result.
This is joint work with Martin Rolek. (TCPL 201) |

15:30 - 15:50 | Coffee Break (TCPL Foyer) |

15:50 - 16:10 |
Sang-il Oum: Chi-boundedness of graph classes excluding wheel vertex-minors ↓ A class of graphs is \(\chi\)-bounded if there exists a function \(f:\mathbb{N}→\mathbb{N}\) such that
for every graph \(G\) in the class and every induced subgraph \(H\) of \(G\), if \(H\) has no
clique of size \(q+1\), then the chromatic number of \(H\) is less than or equal
to \(f(q)\). We denote by \(W_n\) the wheel graph on \(n+1\) vertices. We show that the
class of graphs having no vertex-minor isomorphic to \(W_n\) is \(\chi\)-bounded. This
generalizes several previous results; \(\chi\)-boundedness for circle graphs,
for graphs having no \(W_5\) vertex-minors, and for graphs having no fan
vertex-minors.
This is joint work with Hojin Choi, O-joung Kwon, and Paul Wollan. (TCPL 201) |

16:10 - 16:30 |
Nicolas Trotignon: Polynomial chi-boundedness ↓ A graph $G$ is $\chi$-bounded by the function $f$ if every
induced subgraph $H$ of $G$ satisfied $\chi(H) \le f(\omega(H))$. A class
of graphs is $\chi$-bounded if there exists a function $f$ such that
every graph in the class is $\chi$-bounded by $f$. It is polynomially
$\chi$-bounded if there is such a function $f$ that is a polynomial.
Some classes of graphs are $\chi$-bounded, some are not. It is not
known whether there exists a hereditary class of graph that is
$\chi$-bounded but not polynomially $\chi$-bounded.
The goal of this talk is to survey several results, proof
techniques, and open questions around the notion of polynomial
$\chi$-boundedness. (TCPL 201) |

16:30 - 17:30 |
Alex Scott: Holes in graphs of large chromatic number ↓ Let G be a graph with large chromatic number. What induced subgraphs must
it contain? It may contain a large complete subgraph, but what can we say
if this is not the case? We will survey recent work on this topic,
concentrating on the question of finding induced cycles. In particular, we
will discuss recent results with Paul Seymour, Maria Chudnovsky and Sophie
Spirkl. (TCPL 201) |

17:30 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

19:30 - 20:30 | Problem session (TCPL 201) |

Tuesday, August 22 | |
---|---|

07:00 - 09:00 | Breakfast (Vistas Dining Room) |

09:00 - 10:00 | Stephan Thomasse: The Sands-Sauer-Woodrow conjecture (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 10:50 |
Petr Hlineny: Towards a structure theorem for crossing-critical graphs ↓ We will report on recent significant progress towards a structural
description of large enough $k$-crossing-critical graphs, for every fixed
$k>1$. (TCPL 201) |

10:50 - 11:10 |
János Pach: Crossing numbers ↓ One of the most useful tools in topological graph theory is the so-called
Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi (1982) and Leighton
(1983). It states, roughly speaking, that if a graph drawn in the plane has
much more edges than vertices, then the number of crossings between its
edges is much larger than the number of edges. We extend this result to
simple topological multigraphs, that is, for multigraphs drawn in the plane
such that (1) any two independent edges meet in at most one point, (2) no
two edges that share an endpoint have any interior point in common, and (3)
both lenses enclosed by two edges that have
the same endpoint contain at least one vertex in their interiors. Joint work
with Geza Toth. (TCPL 201) |

11:10 - 11:30 |
Alan Arroyo: Characterizing pseudolinear drawings of graphs in the plane ↓ A drawing of a graph in the plane is pseudolinear if every edge can be
extended to an open arc that separates the plane into two regions such that
any two such arcs have exactly one point in common and that common point is
a crossing. We characterize pseudolinear drawings in terms of forbidden
subconfigurations. A polynomial time algorithm for finding either the
extensions or a forbidden subconfiguration is also given. (TCPL 201) |

11:30 - 13:30 | Lunch (Vistas Dining Room) |

14:30 - 14:50 |
Martin Tancer: Shortest path embeddings of graphs on surfaces ↓ The classical theorem of Fary states that every planar graph can be
represented by an embedding in which every edge is represented by a straight
line segment. We consider generalizations of Fary's theorem to surfaces
equipped with Riemannian metrics. In this setting, we require that every
edge is drawn as a shortest path between its two endpoints and we call an
embedding with this property a shortest path embedding. The main question
considered in the talk is whether given a closed surface \(S\), there exists a
Riemannian metric for which every topologically embeddable graph admits a
shortest path embedding. This question is also motivated by various problems
regarding crossing numbers on surfaces.
It is easy to observe that the round metrics on the sphere and the
projective plane have this property. We provide flat metrics on the torus
and the Klein bottle which also have this property. On the other hand the
unit square flat metric on the Klein bottle there exists a graph without
shortest path embeddings.
For large \(g\), there exist graphs \(G\) embeddable into the orientable surface of
genus \(g\), such that with large probability a random hyperbolic metric does
not admit a shortest path embedding of \(G\) (w.r.t. the Weil-Petersson volume
on moduli space). On the other hand, it is possible to construct a
hyperbolic metric on every orientable surface \(S\) of genus \(g\), such that every
graph embeddable into \(S\) can be embedded so that every edge is a
concatenation of at most \(O(g)\) shortest paths.
Joint with A. Hubard, V. Kaluza, A. de Mesmay. (TCPL 201) |

14:50 - 15:10 |
Jan Kyncl: Counterexample to the Hanani-Tutte theorem on the surface of genus 4 ↓ We find a graph of genus 5 and its drawing on the orientable surface of
genus 4 with every pair of independent edges crossing an even number of
times. This shows that the strong Hanani-Tutte theorem cannot be generalized
to the orientable surface of genus 4. As a base step in the
construction we use a counterexample to the unified Hanani-Tutte theorem on
the torus.
The result was obtained together with Radoslav Fulek. (TCPL 201) |

15:10 - 15:30 |
Radoslav Fulek: Hanani-Tutte for approximating maps of graphs ↓ We resolve in the affirmative conjectures of
A. Skopenkov and Repovs (1998), and M. Skopenkov (2003) generalizing the
classical Hanani--Tutte theorem to the setting of approximating maps of
graphs in the plane by embeddings. Our proof of this result is constructive,
and implies the existence of a polynomial-time algorithm for the following
problem.
An instance of the problem consists of (i) a graph $G$ whose vertices are
partitioned into clusters and whose inter-cluster edges are partitioned into
bundles, and (ii) a 2-dimensional surface $S$ given as the union of a set of
pairwise disjoint discs corresponding to the clusters and a set of pairwise
non-intersecting strips, ``pipes'', corresponding to the bundles, connecting
certain pairs of these discs.
We are to decide whether $G$ can be embedded inside $S$ so that the vertices
in every cluster are drawn in the corresponding disc, the edges in every
bundle pass only through its corresponding pipe, and every edge crosses the
boundary of each disc at most once.
Joint work with J. Kyncl. (TCPL 201) |

15:30 - 16:00 | Coffee Break (TCPL Foyer) |

16:00 - 16:45 |
Daniela Kuhn: Proof of the tree packing conjecture for bounded degree trees ↓ We prove that given any sequence of $n$ bounded degree trees so that the $j$th
tree has $j$ vertices, the complete graph on $n$ vertices has a decomposition
into these trees, if $n$ is large enough. This shows that the tree packing conjecture of Gyarfas and
Lehel from 1976 holds for all bounded degree trees.
An important ingredient is a new tool for constructing approximate
decompositions of dense quasirandom graphs into bounded degree graphs (which
can be viewed as an extension of the classical blow-up lemma of Komlos,
Sarkozy and Szemeredi to the setting of approximate decompositions).
(Joint work Felix Joos, Jaehoon Kim, Deryk Osthus and Mykhaylo Tyomkyn) (TCPL 201) |

16:45 - 17:30 |
Deryk Osthus: Hypergraph $F$-designs exist for arbitrary $F$ ↓ We show that given any $r$-uniform hypergraph $F$, the trivially necessary
divisibility conditions are sufficient to guarantee a decomposition of any
sufficiently large complete $r$-uniform hypergraph into edge-disjoint copies
of $F$.
The case when $F$ is complete corresponds to the existence of block designs, a
problem going back to the 19th century, which was recently settled by
Keevash. In particular, our argument provides a new proof of this result,
which employs purely probabilistic and combinatorial methods. We also obtain
several further generalizations.
(Joint work with Stefan Glock, Daniela Kuhn and Allan Lo.) (TCPL 201) |

17:30 - 19:30 | Dinner (Vistas Dining Room) |

Wednesday, August 23 | |
---|---|

07:00 - 09:00 | Breakfast (Vistas Dining Room) |

09:00 - 10:00 |
Xingxing Yu: The Kelmans-Seymour conjecture ↓ Seymour and, independently, Kelmans conjectured that every
5-connected non-planar
graph contains a subdivision of $K_5$. We have recently proved this
conjecture. I will give a sketch of our proof, and mention several related
problems. Joint work with D. He and Y. Wang. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 10:50 |
Chun-Hung Liu: Packing topological minors half-integrally ↓ The packing problem and the covering problem are two general optimization
problems that form a pair of dual integer programming problems. Fix a family
\(F\) of graphs, the packing problem asks for the maximum number of disjoint
subgraphs of the input graph \(G\) where each is isomorphic to a member of \(F\), and
the covering problem asks for the minimum number of vertices of \(G\) required
to intersect all such subgraphs. We say \(F\) has the Erdos-Posa property if the
solutions of these two problems with respect to \(F\) can be bounded in terms of
each other. It is well-known that if \(H\) is a graph such that the set of \(H\)
minors has the Erdos-Posa property, then \(H\) must be planar. Thomas
conjectured that the planarity is not required if half-integral solutions of
the packing problem are allowed. In other words, he conjectured that for
every graph \(H\), there exists a function \(f\) such that for every graph \(G\), either
\(G\) contains \(k\) subgraphs where each of them is an \(H\) minor such that every
vertex of \(G\) is contained in at most two of those subgraphs, or there exists
a set of at most \(f(k)\) vertices intersecting all \(H\) minors in \(G\). In this talk,
we prove that the same statement holds for topological minors. It is a
stronger statement that easily implies Thomas' conjecture. Namely, we prove
that for every graph \(H\), there exists a function \(f\) such that for every graph
\(G\), either \(G\) contains \(k\) subdivisions of \(H\) such that every vertex of \(G\) is
contained in at most two of them, or there exists a set of at most \(f(k)\)
vertices intersecting all subdivisions of \(H\) in \(G\). (TCPL 201) |

10:50 - 11:10 |
Zdenek Dvorak: Classes of graphs with strongly sublinear separators ↓ Classes of graphs with strongly sublinear separators (i.e., separators
of order at most \(n^{1-\epsilon}\) for some \(\epsilon>0)\) have important
algorithmic
and structural properties. We explore some of these properties, especially
in relation to polynomial expansion and tree-width fragility. (TCPL 201) |

11:10 - 11:30 |
Bojan Mohar: Maximum number of colourings and Tomescu's conjecture ↓ It is proved that every connected graph $G$ on $n$ vertices with $\chi(G)
\geq 4$ has at most $k(k-1)^{n-3}(k-2)(k-3)$ $k$-colourings for every $k
\geq 4$.
Equality holds for some (and then for every) $k$ if and only if the graph is
formed from $K_4$ by repeatedly adding leaves.
This confirms (a strengthening of) the $4$-chromatic case of a long-standing
conjecture of Tomescu [Le nombre des graphes connexes $k$-chromatiques
minimaux aux sommets etiquetes, C. R. Acad. Sci. Paris 273 (1971),
1124--1126]. Proof methods may be of independent interest. In particular,
one of our auxiliary results about list-chromatic polynomials solves a
recent conjecture of Brown, Erey, and Li.
(Joint work with Fiachra Knox.) (TCPL 201) |

11:30 - 13:30 | Lunch (Vistas Dining Room) |

13:30 - 17:30 | Free Afternoon (Banff National Park) |

17:30 - 19:30 | Dinner (Vistas Dining Room) |

Thursday, August 24 | |
---|---|

07:00 - 09:00 | Breakfast (Vistas Dining Room) |

09:00 - 10:00 |
Maria Chudnovsky: Coloring graphs with forbidden induced subgraphs ↓ The problem of testing if a graph can be colored with a given number $k$ of
colors is NP-complete for every $k>2$. But what if we have more information
about the input graph, namely that some fixed graph $H$ is not present in it
as an induced subgraph? It is known that the problem remains NP-complete
even for $k=3$, unless $H$ is the disjoint union of paths. We consider the
following two questions:
1. For which graphs $H$ is there a polynomial time algorithm to 3-color
(or in general $k$-color) an $H$-free graph?
2. For which graphs $H$ are there finitely many 4-critical $H$-free graphs?
This talk will survey recent progress on these questions, and in particular
give a complete answer to the second one. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 10:50 |
Frederic Maffray: A coloring algorithm for $4K_1$-free line graphs ↓ When $F$ is a set of four-vertex graphs the complexity of the vertex coloring
problem in the class of $F$-free graphs is known, with three exceptions: $F =
\{\text{claw}, 4K_1\}$, $F = \{\text{claw}, 4K_1, \text{co-diamond}\}$, and $F = \{C_4, 4K_1\}$. We study the
coloring problem for $\{\text{claw},4K_1\}$-free graphs. We solve the vertex coloring
problem for a subclass of this class which contains the class of $4K_1$-free
line graphs. Our result implies that the chromatic index of a graph with no
matching of size four can be computed in polynomial time.
Joint work with Dallas J. Fraser, Angele M. Hamel, Chinh T. Hoang
(Department of Physics and Computer Science, Wilfrid
Laurier University, Waterloo, Ontario, Canada) (TCPL 201) |

10:50 - 11:10 |
Ngoc Khang Le: Detecting an induced subdivision of \(K_4\) ↓ We propose a polynomial-time algorithm to test whether a given
graph contains a subdivision of \(K_4\) as an induced subgraph. This continues
the study of detecting an induced subdivision of \(H\) for some fixed graph
\(H\), which is still far from being complete. Our result answers a question
posed by Chudnovsky et al. and Lévêque et al. (TCPL 201) |

11:10 - 11:30 |
Sophie Spirkl: $P_6$-free triangle-free graphs ↓ I will talk about an explicit construction for triangle-free graphs that do
not contain a six-vertex path as an induced subgraph. Examples include the
16-vertex Clebsch graph, and the graph that arises from a complete bipartite
graph by subdividing every edge of a perfect matching exactly once. We show
that every connected triangle-free graph with no six-vertex induced path can
be obtained from an induced subgraph of one of these two by restricted
homogeneous set and homogeneous pair operations.
Joint work with Maria Chudnovsky, Paul Seymour, and Mingxian Zhong. (TCPL 201) |

11:30 - 13:30 | Lunch (Vistas Dining Room) |

14:30 - 15:30 |
Kristina Vuskovic: (Theta, wheel)-free graphs ↓ A theta is a subdivision of $K_{2,3}$, and a wheel is a graph that consist of a chorldless cycle of length at least 4 and a vertex that has at least 3 neighbors on the cycle. In recently completed joint work with Trotignon and Radovanovic we obtained a structure theorem for graphs that do not contain thetas and wheels as induced subgraphs (i.e. (theta, wheel)-free graphs) and several of its algorithmic consequences.
(TCPL 201) We decompose (theta, wheel)-free graphs using clique cutsets and 2-joins into graphs that are essentially formed of a line graph of a triangle-free chordless graph plus a (possibly empty) clique (that attaches to the rest of the graph in a particular way). A 2-join is an edge cutset that appears in decomposition theorems for several complex hereditary classes, such as perfect graphs, even-hole-free graphs and others. In these decomposition theorems 2-joins are used together with vertex cutsets that are stronger than clique cutsets, such as star cutsets and their generalizations (which are much harder to use in algorithms). This is a first example of a decomposition theorem that uses just the combination of clique cutsets and 2-joins. This has several consequences. First, we can easily transform our decomposition theorem into a complete structure theorem for (theta, wheel)-free graphs, i.e. we show how every graph in the class can be built starting from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations, and all graphs built this way are in the class. Such structure theorems are rare for hereditary graph classes, only a few examples are known. Next, we construct a polynomial-time decomposition-based recognition algorithm. Recognizing classes of graphs defined by excluding different combinations of Truemper configurations (i.e. wheels, thetas, prisms and pyramids) is a much studied problem. For some combinations the problem is known to be polynomial (e.g. recognizing pyramids and thetas), whereas for others it is NP-complete (e.g. recognizing prisms and wheels). The class of (theta, wheel)-free graphs was the last of these types of recognition problems that was open, and we now resolve. We then use the decomposition theorem to obtain polynomial-time algorithms for weighted stable set, weighted clique and vertex coloring problems. For the weighted stable set problem, it was essential to decompose the graph using a sequence of non-crossing 2-joins. The weighted clique problem we solve by first showing the existence of a bisimplicial vertex (a vertex whose neighborhood partitions into 2 cliques). This is done elegantly by using the existence of an extreme 2-join (a 2-join whose one block of decomposition does not have a 2-join). We also prove that every (theta, wheel)-free graph with maximum clique size $\omega$ admits a coloring with at most max$\{\omega ,3\}$ colors. Finally, we obtain a polynomial-time algorithm for the induced version of the $k$-linkage problem (for fixed $k$): given $k$ distinct pairs of vertices $(s_i,t_i)$ of a graph $G$, decide whether there are $k$ vertex-disjoint paths $P_i=s_i \ldots t_i$, $i=1, \ldots ,k$, such that there are no edges between the vertices of these paths. |

15:30 - 16:00 | Coffee Break (TCPL Foyer) |

16:00 - 16:30 |
Luke Postle: On a local version of Reed's conjecture ↓ In 1998, Reed conjectured that the chromatic number of a graph is
at most the average of its maximum degree plus one and its clique number
(rounded up). As evidence for his conjecture, he proved that it is at most
some non-trivial convex combination of the two. Recently, Michelle Delcourt
and I proved the same is true for list chromatic number. Tom Kelly and I
meanwhile conjectured that a `local' version of Reed's conjecture wherein
the parameters are replaced by local parameters (list size, degree and
clique number of neighborhood) and proved a non-trivial convex combination
under some mild assumptions. (TCPL 201) |

16:30 - 17:30 |
Jacob Fox: Tools in discrete geometry ↓ This talk will be about how a diverse set of tools can be used to
make substantial progress on extremal and computational problems in discrete
geometry. In particular, I will discuss
variants of Szemeredi's celebrated graph regularity lemma with much better
quantitative bounds and their applications. This is mostly based on joint
works with Janos Pach and Andrew Suk. (TCPL 201) |

17:30 - 19:30 | Dinner (Vistas Dining Room) |

Friday, August 25 | |
---|---|

07:00 - 09:00 | Breakfast (Vistas Dining Room) |

09:00 - 12:00 | Discussion groups (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

11:30 - 12:00 |
Checkout by Noon ↓ 5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon. (Front Desk - Professional Development Centre) |

11:30 - 13:30 | Lunch from 11:30 to 13:30 (Vistas Dining Room) |