2026 CMS Summer Meeting

Saint John, June 5 - 8, 2026

Submission Form Plenary, Prize and Public Lectures By session By speaker Posters

Structural and Algorithmic Graph Theory
Org: Ben Cameron (University of Prince Edward Island), Alexander Clow (Simon Fraser University) and Margaret-Ellen Messinger (Mount Allison University)
[PDF]

IAIN BEATON, Acadia University $k$-vertex-critical graphs in $(P_4+\ell P_1)$-free graphs [PDF]

A graph $G$ is $k$-vertex-critical if $\chi(G)=k$ but $\chi(G -v) < k$ for all $v\in V(G)$. In this presentation we make progress on the open problem of the finiteness of $k$-vertex-critical $(P_4+\ell P_1)$-free graphs by showing that there are only finitely many $k$-vertex-critical $(P_4+\ell P_1,2P_2)$-free graphs, $(P_4+\ell P_1,\text{chair})$-free graphs, and $(P_4+\ell P_1,P_5,\text{cricket})$-free graphs for all $k\ge 1$ and $\ell\ge 0$. Our results imply the existence of simple polynomial-time certifying algorithms to decide the $k$-colourability of all graphs in these subfamilies for every fixed $k$. This is joint work with Dr. Ben Cameron.

BEN CAMERON, UPEI An infinite family of $k$-critical $(2P_3, K_{k-1})$-free graphs for each $k\ge 5$ [PDF]

In 2020, Chudnovsky, Goedgebeur, Schaudt, and Zhong showed that there are only finitely many $4$-critical $H$-free graphs if and only if $H$ is is an induced subgraph of $P_6$, $2P_3$, or $P_4+\ell P_1$ for some natural number $\ell$. This led to substantial efforts to classify which of these induced subgraphs can be forbidden to leave only finitely many $k$-critical graphs for every $k\ge 4$. Much of this work has focused on subfamilies of $P_6$-free graphs, with some more very recent attention on subfamiles of $(P_4+\ell P_1)$-free graphs. However, very little has been done on subfamilies of $2P_3$-free graphs. In this talk, we will construct an infinite family of $k$-critical $(2P_3,K_{k-1})$-free graphs for each $k\ge 5$.

(This is joint work with Iain Beaton)

MACKENZIE CARR, Toronto Metropolitan University Reconstructing $C_4$-free graphs from their digital convexity [PDF]

Fomin, Kratochv\'il, Lokshtanov, Mancini, and Telle showed that every $C_4$-free graph is reconstructible from the multiset of closed neighborhoods. We strengthen their result, proving that every $C_4$-free graph is reconstructible from the set of closed neighborhoods. A subset $S$ of vertices in a graph $G$ is digitally convex if, for every $v \not\in S$, there is a private neighbor of $v$ with respect to $S$. We establish that reconstruction from digitally convex sets is equivalent to reconstruction from the set of closed neighborhoods, thereby extending the work of Lafrance, Oellermann, and Pressey by showing that all $C_4$-free graphs, and hence all graphs of girth at least five, are reconstructible from their digitally convexity.

This is joint work with Steffen Borgwardt, Ce Chen, Wayne Ge, Stephen G. Hartke, Yixuan Huang and Alex Moon.

NANCY CLARKE, Acadia University Polychromatic Dominating Sets [PDF]

For a graph $G$ with a (not necessarily proper) vertex colouring, a set $D\subseteq V(G)$ is a polychromatic dominating set of $G$ if it is a dominating set and each vertex in $D$ is a different colour. Our parameter of interest is the polychromatic domination number of $G$, $\rho(G)$, defined to be the minimum number of colours such that, for any $\rho(G)$-colouring (with exactly $\rho(G)$ colours) of the vertices of $G$, there exists a polychromatic dominating set. In this talk, we present a variety of results including exact values of our parameter for several classes of graphs and, more generally, tight upper and lower bounds which are functions of the minimum degree of $G$. This is joint work with B Claiborne, R Haas, S Hanson, M Harris, K Martin, S Viel, and J Woods.

ALEXANDER CLOW, Simon Fraser University An Algorithm for the Small Quasi-Kernels Conjecture [PDF]

In a digraph $D$, a quasi-kernel is an independent set $Q$ such that for every vertex $u$, there is a vertex $v \in Q$ satisfying $\text{dist}(v,u)\leq 2$. In 1974 Chvátal and Lovász showed every digraph contains a quasi-kernel. In 1976, P. L. Erdős and Szákely conjectured that every sourceless digraph has a quasi-kernel of order at most $\frac{n}{2}$. Despite significant recent attention by the community the problem remains far from solved, with no bound of the form $(1-\epsilon)n$ known. We introduce a polynomial time algorithm which greedily constructs a small quasi-kernel. Using this algorithm we prove that for any sourceless digraph $D$ with maximum out-degree $3$ contains a quasi-kernel of order at most ${4n}/{7}$.

JULIEN CODSI, Princeton University A Tale of the Tree-Independence Number [PDF]

Treewidth is a graph parameter commonly used to quantify how "close" a graph is to a tree. Although it is a cornerstone of structural graph theory and algorithm design, it is nearly useless for algorithmic purposes in many dense graph classes. In this talk, we discuss the tree-independence number, a more versatile graph parameter that replaces the standard width measure with the stability number. We will present recent results aimed at characterizing the graph classes in which this parameter enables sub-exponential time algorithms for problems that are, in general, NP-hard.

KAREN COLLINS, Wesleyan University Partitioned Split Graphs [PDF]

A graph $G$ is a split graph if its vertex set can be partitioned into a clique $K$ and a stable set $S$. Thus, the complement of a split graph is also a split graph. Unbalanced partitioned split graphs have a swing vertex that can move from either $K$ to $S$ (or $S$ to $K$), while balanced partitioned split graphs have a unique partition. For a fixed choice of $K$ and $S$, we define $G_{(K,S)} $ to be a partitioned split graph.

We discuss the action of three natural operators on the class of partitioned split graphs. The \emph{inverse operator}, $Inv (G_{(K,S)})$, is the partitioned split graph that results from removing all edges within $K$ and adding all edges between vertices $S$. The \emph{swing operator}, $Sw(G_{(K,S)})$, is the partitioned split graph that results from moving a swing vertex from $K$ to $S$ (or $S$ to $K$) if $G_{(K,S)}$ is unbalanced, and the identity map otherwise. The \emph{complementary operator} of a partitioned split graph, $Comp(G_{(K,S)})$, is the graph complement, keeping the partition, so that the vertices in $K$ become the stable set and the vertices in $S$ become the clique.

These operators generate a group $\Gamma$ on the class of partitioned split graphs. We show that there are graphs with all possible orbit sizes by dividing the class of partitioned split graphs into nine natural subclasses and describing the action of $\Gamma$ between the classes.

\medskip

Joint work with Ann Trenk, Wellesley College and Tantan Dai, Georgia Institute of Technology.

GENA HAHN, Université de Montréal Resurrection II - revisiting old problems [PDF]

Following Ressurrection at CMS 2024 in Vancouver, we continue with reminders of old problems that I think still merit attention, this time including infinite graphs.

SEAN KIM, Simon Fraser University Lower Bound on Degenerate Induced Subgraphs [PDF]

Let $G$ be a graph and let $k,d$ be non-negative integers such that $k \ge d$. We define $\alpha_d(G)$ to be the order of the largest $d$-degenerate induced subgraph of $G$ and $\alpha_d(k) = \inf_\text{G with degeneracy k} \left\{\frac{\alpha_d(G)}{\vert V(G) \vert} \right\}$. There has been a good amount of research done on $\alpha_d$ in the planar graph case, however, not much has been done in the general case. In this talk, we will discuss results on lower bounding $\alpha_d$ for the general graph case, as well as a conjecture on $\alpha_1(2)$.

TAITE LAGRANGE, University of Waterloo When the twin-width is sub-linear [PDF]

Twin-width is a graph and matrix parameter that was introduced in 2021 by Bonnet, Kim, Thomass\'e, and Watrigant as essentially a measure of the accumulated 'error’ between vertex neighbourhoods over a series of vertex contractions. This talk focuses on when the twin-width of a graph class can be bounded by some sub-linear function on the number of vertices. We present a technique for obtaining twin-width bounds in general by contracting a graph based on a partition by distinct neighbourhoods and use this to give a sub-linear upper bound on the twin-width of graphs of bounded VC-dimension, a parameter which can be formulated for graphs to measure the structural complexity of vertex neighbourhoods. Our result implies that a hereditary class of graphs $\mathcal{C}$ has sub-linear twin-width if and only if $\mathcal{C}$ has bounded VC-dimension.

This is joint work with Therese Biedl and Sophie Spirkl.

EDUARDO MARTINEZ-PEDROZA, Memorial Universiity Gromov’s Approximating Tree and the All-pairs Bottleneck Paths Problem. [PDF]

Let $X$ be a simple connected graph on $n+1$ vertices. The Gromov hyperbolicity constant $\delta\geq0$ measures ”tree-likeness” of $X$. For a fixed vertex $w$, the Gromov approximating tree of $(X, w)$ is an optimal tree $T$ whose vertex set contains that of $X$, such that distances to the root are preserved, $\mathsf{dist}_X(x, w) = \mathsf{dist}_T (x, w)$, and pairwise distances satisfy $\mathsf{dist}_X(x, y) - 2\delta \log_2 n \leq \mathsf{dist}_T (x, y) \leq \mathsf{dist}_X(x, y)$ for all $x, y \in X$.

We present an explicit algorithm that constructs Gromov approximating tree of $(X, w)$ from the adjacency matrix of the graph in quadratic time. Our approach reduces the construction of the tree to the All-Pairs Bottleneck Paths (APBP) problem for a weighted graph on n vertices, which is known to be solvable in $O(n^2)$ time.

Joint work with Anders Cornect.

MARGARET-ELLEN MESSINGER, Mount Allison University Domination reconfiguration: a mixed model [PDF]

Let $G$ be a graph. A domination reconfiguration graph of $G$ is a graph whose vertices correspond to the dominating sets of $G$. Adjacencies are typically determined by using either the token addition/removal (TAR) or the token sliding (TS) rule. While the domination reconfiguration graph obtained by using only the TAR rule will never have a Hamilton cycle, we show that for some classes of graphs $G$, by adding a relatively small number of TS edges, the resulting domination reconfiguration graph is not only hamiltonian, but in fact pancyclic. This is joint work with Logan Pipes (MUN).

BEN SEAMONE, Dawson College Removeable edges in cubic graphs which admit nowhere-zero 4-flows [PDF]

A conjecture by Hoffmann-Ostenhof states that every cubic graph G with a nowhere-zero 4-flow has an edge e such that G - e has a nowhere-zero 4-flow. We present progress on this conjecture.

AGNES TOTSCHNIG, Massachusetts Institute of Technology Almost perfect graph classes [PDF]

Perfect graphs form one of the central graph classes in structural graph theory. Many optimization problems that are hard in general become tractable on them. They are exactly the graphs with no odd holes or odd antiholes. A natural way to relax perfection is to ask whether a graph becomes perfect after deleting only a bounded number of vertices. We call such classes of graphs bounded-apex-perfect. In this talk, we characterize the sets H of at most two forbidden induced subgraphs for which the class of H-free graphs is bounded-apex-perfect. We will also explain how this characterization extends to several important subclasses of perfect graphs, including chordal, bipartite, complete multipartite, interval, and split graphs.

Joint work with Cicely Henderson, Hidde Koerts, Taite LaGrange, Sophie Spirkl, Massimo Vicenzo and Rebecca Whitman.

ANN TRENK, Wellesley College Degree sequences, split graphs and geometric representations [PDF]

A graph is a \emph{split graph} if its vertex set can be partitioned into a clique and a stable set and is a \emph{partitioned split graph} if the partition is also specified. The \emph{inverse} of a partitioned split graph is formed by removing all edges within the clique and adding all edges between vertices in the stable set.

In this talk we consider two forms of the degree sequences of a graph: the conventional form and the block form. We show the effect on the block form of taking complements of graphs and inverses of split graphs, the latter of which is complicated by the fact that some split graphs have two different inverses. When there are two different inverses, we show how the degree sequences of these inverses are related to one another in both the conventional and block forms. We also demonstrate geometric interpretations of these results using Ferrers diagrams.

\medskip

This is joint work with Karen Collins, Wesleyan University and Tantan Dai, Georgia Institute of Technology.

top of page