CanaDAM 2019
SFU Harbour Centre, May 29 - 31, 2019

Matching Theory
Org: Nishad Kothari (University of Campinas)

ROBERT ALDRED, University of Otago
Asymmetric Distance Matching Extension  [PDF]

In 1980, Plummer showed that no planar graph is 3-extendable. Over 20 years later, it was shown that in a 5-connected planar triangulation of even order every induced matching of size 3 extends to a perfect matching. More recently, we have found that we can relax the distance condition so that if $M$ is a matching in an even 5-connected planar triangulation such that at least one of the edges in $M$ is at least distance 2 from the other two, then $M$ extends to a perfect matching. We present this result along with some additional ``asymmetric'' distance matching results.

MARCELO CARVALHO, Federal University of Mato Grosso do Sul (UFMS)
Birkhoff--von Neumann Graphs that are PM-compact  [PDF]

A well-studied object in combinatorial optimization is the perfect matching polytope $\mathcal{PMP}(G)$ of a graph $G$. A graph $G$ is `Birkhoff--von Neumann' if $\mathcal{PMP}(G)$ is characterized solely by non-negativity and degree constraints, and $G$ is `PM-compact' if the combinatorial diameter of $\mathcal{PMP}(G)$ equals one. Each of the corresponding decision problems has a graph-theoretical $co-\mathcal{NP}$ characterization; there is a striking similarity between these characterizations. However, neither of them is known to be in $\mathcal{NP}$. We give a complete characterization of graphs that are Birkhoff--von Neumann as well as PM-compact. Joint work with Nishad Kothari, Xiumei Wang and Yixun Lin (see

PHELIPE FABRES, Federal University of Mato Grosso do Sul (UFMS)
Minimal Braces  [PDF]

A brace is a $2$-extendable bipartite graph. A brace is minimal if the deletion of any edge results in a graph that is not a brace.

We deduce a generation theorem for minimal braces from McCuaig's simple brace generation theorem. As a corollary, we obtain an upper bound of $5n-10$ on the number of edges of a minimal brace of order $2n$, and we provide a complete characterisation of minimal braces that achieve this upper bound. This is joint work with Marcelo H. de Carvalho and Nishad Kothari.

NISHAD KOTHARI, University of Campinas (UNICAMP)
Constructing $K_4$-free bricks that are Pfaffian  [PDF]

Lovász (1983) showed that every nonbipartite matching covered graph contains at least one of $K_4$ and the triangular prism $\overline{C_6}$ as a conformal minor. Kothari and Murty (2016) gave a complete characterization of planar $K_4$-free graphs. It now remains to characterize the nonplanar $K_4$-free bricks. Since then, we have discovered two operations that may be used to construct nonplanar $K_4$-free bricks. These constructions also yields Pfaffian bricks. We conjecture that all $K_4$-free bricks are Pfaffian.

MICHAEL PLUMMER, Vanderbilt University
Distance Matching in Planar Triangulations: some new results  [PDF]

In 2011, it was shown that in a $5$-connected even planar triangulation $G$, every matching $M$ of size less than $\frac{|V(G)|}{2}$ can be extended to a perfect matching of $G$, as long as the edges of $M$ lie at distance at least $5$ from each other.

Later in 2017, Kawarabayashi, Ozeki and the speaker proved a generalization of this result to other surfaces in which ``holes'' in the triangulation were allowed. However, the face-width of the embedded triangulation had to be at least $6$.

Today we present a planar analogue of this result.