D. Cranston

activity

20152026

collaborators

Showing 2024Show all

6 papers · 1 filter

math.CO2024

Sharp Bounds on Lengths of Linear Recolouring Sequences

Stijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston

A recolouring sequence, between $k$ -colourings $α$ and $β$ of a graph $G$ , transforms $α$ into $β$ by recolouring one vertex at a time, such that after each recolouring step we aga…

math.CO2024

10-list Recoloring of Planar Graphs

Daniel W. Cranston

Fix a planar graph $G$ and a list-assignment $L$ with $∣ L (v) ∣ = 10$ for all $v \in V (G)$ . Let $α$ and $β$ be $L$ -colorings of $G$ . A recoloring sequence from $α$ to $β$ is a sequence…

cs.DS2024

A simple quadratic kernel for Token Jumping on surfaces

Daniel W. Cranston, Moritz Mühlenthaler, Benjamin Peyrille

The problem \textsc{Token Jumping} asks whether, given a graph $G$ and two independent sets of \emph{tokens} $I$ and $J$ of $G$ , we can transform $I$ into $J$ by changing the posit…

math.CO2024

Planar Graphs with Homomorphisms to the 9-cycle

Daniel W. Cranston, Jiaao Li, Zhouningxin Wang +1

We study the problem of finding homomorphisms into odd cycles from planar graphs with high odd-girth. The Jaeger-Zhang conjecture states that every planar graph of odd-girth at lea…

cs.DM2024

Token Jumping in Planar Graphs has Linear Sized Kernels

Daniel W. Cranston

Let $G$ be a planar graph and $I_{s}$ and $I_{t}$ be two independent sets in $G$ , each of size $k$ . We begin with a "token" on each vertex of $I_{s}$ and seek to move all tokens to $I_{t}$ …

math.CO2024

List Packing and Correspondence Packing of Planar Graphs

Daniel W. Cranston, Evelyne Smith-Roberge

For a graph $G$ and a list assignment $L$ with $∣ L (v) ∣ = k$ for all $v$ , an $L$ -packing consists of $L$ -colorings $φ_{1}, \dots, φ_{k}$ such that $φ_{i} (v) \neq = φ_{j} (v)$ for all $v$ and all dis…