CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Théorie des graphes structurelle
Responsable et président: Luke Postle (University of Waterloo, Canada)

ZDENEK DVORAK, Charles University in Prague
Structure of graphs with forbidden strong immersion  [PDF]

A graph $H$ is contained in $G$ as an immersion if vertices of $H$ are injectively mapped to vertices of $G$ (the branch vertices) and the edges of $H$ correspond to pairwise edge-disjoint paths joining the corresponding branch vertices. The immersion is strong if additionally the paths do not pass through the branch vertices. We give an approximate structure for graphs that avoid $K_n$ as a strong immersion.

The talk is based on a joint work with Paul Wollan.

MARK ELLINGHAM, Vanderbilt University
Excluding small minors of connectivity 2  [PDF]

Ding and Liu have systematically studied the families of graphs obtained by excluding each small $3$-connected graph as a minor. We have done the same for small graphs of connectivity $2$, and we report on the results. This is joint work with Emily Marshall, Tom McCourt and Tony Nixon.

NISHAD KOTHARI, University of Waterloo
Generating near-bipartite bricks  [PDF]

A $3$-connected graph $G$ is a brick if for any two vertices $u$ and $v$, graph $G-\{u,v\}$ has a perfect matching. A brick $G$ is near-bipartite if it has two edges $e$ and $f$ such that $G-\{e,f\}$ is bipartite and matching covered. For example, (nonbipartite) Mobius ladders and prisms are near-bipartite bricks, whereas Petersen graph is not.

Carvalho, Lucchesi and Murty showed that all bricks may be generated from three~bricks, namely $K_4$, triangular~prism~$\overline{C_6}$ and Petersen graph. Likewise, we show that all near-bipartite bricks may be generated from $K_4$ and $\overline{C_6}$ by means of three operations.

Some applications will be discussed.

CHUN-HUNG LIU, Princeton University
Erdos-Posa property for topological minors  [PDF]

A family ${\mathcal F}$ of graphs has the Erd\H{o}s-P\'{o}sa property if there exists a function $f$ such that for every integer $k$, every graph either contains $k$ disjoint subgraphs each isomorphic to a member of ${\mathcal F}$ or contains $f(k)$ vertices that intersect in every subgraph isomorphic to a member of ${\mathcal F}$. We will characterize the graphs $H$ for which ${\mathcal T}(H)$ has the Erd\H{o}s-P\'{o}sa property, where ${\mathcal T}(H)$ is the set of graphs containing $H$ as a topological minor, answering a question of Robertson and Seymour. This work is joint with Luke Postle and Paul Wollan.

BOJAN MOHAR, Simon Fraser University
On a problem of Erdos and Neumann-Lara  [PDF]

The dichromatic number of a graph G is the maximum integer k such that there exists an orientation of the edges of G such that for every partition of the vertices into fewer than k parts, at least one of the parts must contain a directed cycle under this orientation. In 1979, Erd\H os and Neumann-Lara conjectured that if the dichromatic number of a graph is bounded, so is its chromatic number. We make the first significant progress on this conjecture by proving a fractional version of the conjecture. This is a joint work with Hehui Wu (University of Mississipi).


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Saskatchewan