CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Structure of graphs I
Président: David Wood (Monash University)

MARK ELLINGHAM, Vanderbilt University
The structure of $4$-connected $K_{2,t}$-minor-free graphs  [PDF]

Guoli Ding has provided a rough structure theorem for $K_{2,t}$-minor free graphs for all $t$. As a special case of his theorem, $4$-connected $K_{2,t}$-minor-free graphs are obtained by attaching strips, consisting of two paths joined by edges with restricted crossings, to a finite set of base graphs. The first value of $t$ where this applies in a nontrivial way is $t=5$. We give a characterization of $4$-connected $K_{2,5}$-minor-free graphs that shows that they can be obtained from a cyclic sequence of four types of subgraph. Consequently, we can derive a generating function and asymptotic estimate for the number of nonisomorphic $4$-connected $K_{2,5}$-minor-free graphs of a given order. Our work extends to general $t$ by providing a more precise description of the strips in Ding's result, suggesting a general asymptotic counting conjecture.

This is joint work with J. Zachary Gaslowitz.

CHEOLWON HEO, University of Waterloo
Signed graphs with the same even cycles  [PDF]

A signed graph $(G,\Sigma)$ is a pair of a graph $G$ and a subset $\Sigma$ of edges of $G$. We say that $C \subseteq E(G)$ is an even cycle if $G[C]$ is Eulerian, and $|C \cap \Sigma|$ is even. This talk is about the even cycle isomorphism problem - What is the relationship between two signed graphs $(G_1, \Sigma_1)$ and $(G_2, \Sigma_2)$ that have the same even cycles. In his doctoral thesis, Shih solved the even cycle isomorphism problem when either $\Sigma_1$ or $\Sigma_2$ is the empty set. I will introduce a generalized result of this under some connectivity assumption. This is joint work with Bertrand Guenin and builds on an earlier result with Irene Pivotto.

DAVID KIRKPATRICK, University of British Columbia
Isolated Perfect Matchings  [PDF]

A perfect matching $M$ of a graph $G$ is \emph{$k$-isolated} if, for every other perfect matching $M'$, the symmetric difference $M\Delta M'$ satisfies $|M\Delta M'|\ge2k$.

It is straightforward to efficiently test if a perfect matching--which if one exists can be efficiently constructed--is unique (or $\infty$-isolated). Similarly, if $G$ has maximum degree 2, it is straightforward to efficiently determine the largest $k$ for which G admits a $k$-isolated perfect matching. In contrast, we show that testing if a given bipartite G, of maximum degree 3, admits a $k$-isolated perfect matching is NP-hard, for every fixed $k>0$.

Isolated perfect matchings are related to the well-studied notion of \emph{induced matchings}, introduced by K. Cameron, and $\delta$-separated matchings, introduced by Stockmeyer-Vazirani, in the 1980s, as models of stability in matchings. They also arise naturally in the study of collusion-free teaching-learning protocols for set-systems.

(Based on joint work with H. Simon and S. Zilles.)

Kempe Chains and Rooted Minors  [PDF]

A transversal of a partition is a set which contains exactly one member from each member of the partition and nothing else. We study the following problem. Given a transversal $T$ of a proper colouring $C$ of order $k$ of some graph $G$, is there a partition $H$ of a subset of $V(G)$ into connected sets such that $T$ is a transversal of $H$ and such that two sets of $H$ are adjacent if their corresponding vertices from $T$ are connected by a path using only two colours?

This is open for each $k \geq 5$; here we consider some positive results if $k=5$ and disprove it for $k=7$.

This is joint work with Matthias Kriesell.

DOUGLAS B. WEST, Zhejiang Normal University and University of Illinois
Cut-edges and Regular Subgraphs in Odd-degree Regular Graphs  [PDF]

Hanson, Loten, and Toft proved that every $(2r+1)$-regular graph with at most $2r$ cut-edges has a $2$-factor. We generalize this by proving for $k\le(2r+1)/3$ that every $(2r+1)$-regular graph with at most $2r-3(k-1)$ cut-edges has a $2k$-factor. The restrictions on $k$ and on the number of cut-edges are sharp. We characterize the graphs with exactly $2r-3(k-1)+1$ cut-edges but no $2k$-factor. For $k>(2r+1)/3$, there are graphs without cut-edges that have no $2k$-factor. (Joint work with Alexandr V. Kostochka, Andr\'e Raspaud, Bjarne Toft, and Dara Zirlin.)

We determine the maximum guaranteed size of a $2$-regular subgraph in a $3$-regular $n$-vertex graph. In particular, we prove that every multigraph with maximum degree $3$ and exactly $c$ cut-edges has a $2$-regular subgraph that omits at most $\max\{0,\lfloor (3n-2m+c-1)/2\rfloor\}$ vertices. The bound is sharp; we describe the extremal multigraphs. (Joint work with Ilkyoo Choi, Ringi Kim, Alexandr V. Kostochka, and Boram Park.)