ThÃ©orie des graphes structurelle
Responsable et prÃ©sident:
Luke Postle (University of Waterloo, Canada)
[
PDF]
 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 edgedisjoint 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 nearbipartite 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 nearbipartite 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 nearbipartite 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 nearbipartite bricks may be
generated from $K_4$ and $\overline{C_6}$ by means of three operations.
Some applications will be discussed.
 CHUNHUNG LIU, Princeton University
ErdosPosa property for topological minors [PDF]

A family ${\mathcal F}$ of graphs has the Erd\H{o}sP\'{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}sP\'{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 NeumannLara [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 NeumannLara 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).