CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Org: Ruth Haas (U. Hawaii, Manoa)

BENJAMIN MOORE, Simon Fraser University
Some observations on circular colouring mixing for $(p,q)$-colourings when $p/q <4$  [PDF]

Let $p$ and $q$ be integers such that $p/q \geq 2$. Let $G$ be a graph and let $\mathcal{C}_{p,q}(G)$ be the graph whose vertex set is all $(p,q)$-colourings of $G$ and two $(p,q)$-colourings are adjacent if they differ in exactly one colour. The $(p,q)$-mixing problem asks if for a given $G$, $p$ and $q$, is $\mathcal{C}_{p,q}(G)$ is connected? This talk discusses results on $(p,q)$-mixing when $p/q <4$. Specifically, a characterization of when $\mathcal{C}_{p,q}$ is connected, and when $p=2k+1$ and $q =k$, that $(p,q)$-mixing is co-NP-complete.

Reconfiguration of Common Independent Sets of Partition Matroids  [PDF]

We investigate the complexity of reconfiguring common independent sets of two or more partition matroids. In particular, we show that deciding the connectivity of two common independent sets of two partition matroids is tractable, while for three or more partition matroids the task becomes PSPACE-complete. The proof of the former result implies that partition matroids are in some sense not more expressive than the restricted class of partition matroids, where at most one item can be chosen from each block of the partition.

Introduction to Reconfiguration  [PDF]

Reconfiguration is concerned with relationships among solutions to a problem instance, where the reconfigration of one solution to another is a sequence of steps such that each step produces an intermediate feasible solution. The solution space can be represented as a graph, where vertices representing two solutions are adjacent if one can be formed from the other in a single step. Work in the area encompasses both structural questions (Is the reconfiguration graph connected?) and algorithmic ones (How can one find the shortest sequence of steps between two solutions?) This talk introduces techniques, results, and future directions in the area.

BETH NOVICK, Clemson University
Structural Properties of Shortest Path Graphs  [PDF]

The reconfiguration version of a problem concerns whether it is possible to move from one feasible solution of that problem to another following some set of reconfiguration rules. One can consider the associated reconfiguration graph with a vertex corresponding to each feasible solution and an edge between two feasible solutions if one can get between them with one application of the reconfiguration rule. In this talk we consider the shortest path reconfiguration graph. We give some structural properties of shortest path graphs including a partial characterization based on girth.

Reconfiguring Vertex Colourings of 2-trees  [PDF]

Let $H$ be a graph and $k\geq \chi(H)$ an integer. The $k$-colouring graph of $H$, denoted $G_k(H)$, has as its vertices the set of all proper $k$-colourings of $H$; two vertices of $G_k(H)$ are adjacent if and only if the corresponding $k$-colourings agree on all except one of the vertices of $H$. Let $k_0(H)$ denote the smallest $k$ for which $G_k(H)$ is hamiltonian. It is known that $k_0(H)\geq \mbox{col}(H) +2$, where $\mbox{col}(H)$ is the colouring number of $H$. We show that if $H$ is a 2-tree, then $k_0(H)=\mbox{col}(H)+2$ or $k_0(H)=\mbox{col}(H)+3$, and characterize the 2-trees in both cases.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology