Schedule for: 17w5154 - Geometric and Structural Graph Theory

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.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

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).

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.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

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!

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.

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.

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. 

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.

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.

We will report on recent significant progress towards a structural description of large enough $k$-crossing-critical graphs, for every fixed $k>1$.

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.

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.

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.

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.

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.

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)

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.)

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.

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\).

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.

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.)

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.

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)

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.

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.

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.

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.

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. 

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.

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.