CanaDAM 2017
Ryerson University, June 12 - 16, 2017

Structural Graph Theory
Org: Luke Postle (Waterloo)

Decomposition into a stable set and a k-degenerate graph  [PDF]

We consider the problem of bipartitioning the vertices of a graph in such a way that the first part induces a stable set and the second a $k$-degenerate graph for some fixed $k$. In particular, we study the complexity of the decision problem when $k=1$ for various graph classes, and provide a quadratic-time algorithm to exhibit such a bipartition when $k=\Delta-2$ and the graph is not complete. This is joint work with Konrad K. Dabrowski, Carl Feghali, Matthew Johnson and Daniël Paulusma.

GUANTAO CHEN, Georgia State University
Goldberg's Conjecture and Tashkinov Trees  [PDF]

Gupta\, (1967), Goldberg\,(1973), Andersen\,(1977), and Seymour\,(1979) conjectured that $\chi'=\lceil\chi_f'\rceil$ if $\chi'\ge \Delta+2$. Inspired by the Tashkinov tree technique, some progress has made toward this conjecture in the last decade. Chen, Gao, Kim, Postle and Shan showed that if $\chi' >\Delta+\sqrt[3]{\Delta/2}$ then $\chi'=\lceil\chi_f'\rceil$. The key technic result of their proof gives a lower bound of the number of edges of a vertex set of a critical graph. Replacing the number of edges by the number of different colors, Chen and Jing recently obtained a stronger result, which can be applicated to improve some other previous results.

ZDENEK DVORAK, Charles University
Thinness of graph classes and approximation algorithms  [PDF]

Baker(1994) found a technique to design polynomial-time approximation algorithms for many problems on planar graphs. This technique also works for graphs avoiding a fixed apex graph as a minor, and with significant extra effort some of the power of the technique can be extended to all proper minor-closed classes. We describe a novel graph decomposition that makes the generalization much easier and more natural, and show that all proper minor-closed graph classes, as well as subgraph-closed classes with strongly sublinear separators and bounded maximum degree admit this decomposition.

DAN KRAL, University of Warwick
Coloring graphs drawn in the plane  [PDF]

One of the oldest topics studied in graph theory concerns coloring vertices of graphs drawn in the plane. In this talk, we will survey open problems and results on several classical types of vertex colorings of plane graphs. In particular, we will focus on cyclic colorings and report about our recent results obtained on this type of coloring.

CHUN-HUNG LIU, Princeton University
Half-integrally packing topological minors  [PDF]

Thomas conjectured that for every graph $H$, there exists a function $f$ such that for every graph $G$, either $G$ contains $k$ subgraphs $G_1,...,G_k$, where each $G_i$ contains an $H$ minor, such that every vertex of $G$ is contained in at most two of $G_1,...,G_k$, or $G$ contains a set of at most $f(k)$ vertices intersecting all $H$ minors in $G$. This conjecture was confirmed by Norin. In this talk, we prove that the same holds for topological minors, which implies Thomas' conjecture.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Ryerson University Office of Naval Research Science and Technology