CanaDAM 2017 Ryerson University, June 12 - 16, 2017 canadam.math.ca/2017
 français conference home canadam home

Reconfiguration
Org: Ruth Haas (U. Hawaii, Manoa)
[PDF]

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.

MORITZ MÃœHLENTHALER, Erlangen-Nurnberg
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.

NAOMI NISHIMURA, Waterloo
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.

KAREN SEYFFARTH, U Calgary
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.