CanaDAM 2021
On-line, May 25 - 28, 2021

In honour of Pavol Hell - Part II
Org: Gena Hahn (Université de Montréal) and Gary MacGillivray (University of Victoria)

RICHARD BREWSTER, Thompson Rivers University
Characterizing Circular Colouring Mixing for $p/q < 4$  [PDF]

Given two graph homomorphisms $f, g : G \to H$, $f$ \emph{reconfigures} to $g$ if $g$ can be obtained from $f$ by successively changing the image of one vertex at a time where all intermediate maps are homomorphisms. Such a sequence is a path in the homomorphism graph $\mathrm{Col}(G,H)$. If $\mathrm{Col}(G,H)$ is connected, then $G$ is \emph{$H$-mixing}. We study mixing when $H$ is a circular clique $G_{p,q}$, characterizing $G_{p,q}$-mixing in terms of the \emph{wind} of cycles in $G$. It is co-NP-complete to determine if $G$ is $C_{k,2k+1}$-mixing, but polynomial time solvable when restricted to planar graphs.

Joint with Benjamin Moore.

CESAR HERNANDEZ-CRUZ, Universidad Nacional Autónoma de México
Strongly Chordal Digraphs  [PDF]

Defining a digraph analogue for a given family of graphs is usually a difficult task; typically there are different ways of doing it, and each one has advantages and disadvantages. In this work we propose what we think is a natural digraph analogue to strongly chordal digraphs, and provide evidence to support this claim.

Our definition considers a general setting where a digraph may have loops at some vertices, which has been useful when defining directed analogues of other graph families (Pavol Hell will discuss some examples in another session).

Joint work with Pavol Hell, Jing Huang and Jephian Lin.

JING HUANG, University of Victoria
Obstructions for local tournament orientation completions  [PDF]

The orientation completion problem for a class of oriented graphs asks whether a partially oriented graph can be completed to an oriented graph in the class. Orientation completion problems have been studied recently for several classes of oriented graphs, yielding both polynomial time solutions as well as NP-completeness results.

Using a structure theorem on local tournaments we obtain the full list of minimal partially oriented graphs that cannot be completed to local tournaments. The result may be viewed as an extension of the well-known forbidden subgraph characterization of proper circular-arc graphs obtained by Tucker. This is joint work with Hsu.

Forbidden Induced Subgraphs for $k$-Nested Interval Graphs  [PDF]

An interval $I$ is properly nested in interval $I’$ if both endpoints of $I$ lie in the interior of $I’$. An interval representation $\cal R$ of a given interval graph $G$ has nesting depth at most $d$ if there is no sequence of $d+1$ properly nested intervals in $\cal R$. We denote by $k$-NestedINT the class of all interval graphs that admit interval representations with nesting depth at most $k$.

The graphs in $1$-NestedINT are known as proper interval graphs. Roberts proved that proper interval graphs are precisely those interval graphs that do not contain a claw ($K_{1,3}$). Combined with the forbidden induced subgraph characterization of general interval graphs, due to Lekkerkerker and Boland, this provides a succinct description of the (infinitely many) minimal forbidden subgraphs that characterize $1$-NestedINT.

We develop a similar description that characterizes $k$-NestedINT, for $k \ge 1$. An explicit description is provided for the case $k=2$, and for fixed $k>2$ an algorithm is described that produces a characterization inductively. This is related to a previous algorithm by Klavik, Otachi, and Sejnoha, but in addition provides a combinatorial characterization.

(Based on joint work with P. Hell, P. Klavik, and Y. Otachi.)

GARY MACGILLIVRAY, University of Victoria
Frugal homomorphisms  [PDF]

For a given positive integer $k$, a homomorphism from a graph $G$ to a graph $H$ is $k$-frugal if, for every $x \in V(G)$, no $y \in V(H)$ is the image of more than $k$ neighbours of $x$. Injective homomorphisms are the same as 1-frugal homomorphisms. We present a dichotomy theorem for $k$-frugal homomorphisms for all $k \geq 2$. This is joint work with Stefan Bard.