The Library
Reconfiguring graph homomorphisms on the sphere
Tools
Tools
Tools
Lee, Jae-Baek, Noel, Jonathan A. and Siggers, Mark (2020) Reconfiguring graph homomorphisms on the sphere. European Journal of Combinatorics, 86 . 103086. doi:10.1016/j.ejc.2020.103086 ISSN 0195-6698.
|
PDF
WRAP-reconfiguring-graph-homomorphisms-sphere-Lee-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (854Kb) | Preview |
Official URL: https://doi.org/10.1016/j.ejc.2020.103086
Abstract
Given a loop-free graph H, the reconfiguration problem for homomorphisms to H (also called H-colourings) asks: given two H-colourings f of g of a graph G, is it possible to transform f into g by a sequence of single-vertex colour changes such that every intermediate mapping is an H-colouring? This problem is known to be polynomial-time solvable for a wide variety of graphs H (e.g. all C4-free graphs) but only a handful of hard cases are known. We prove that this problem is PSPACE-complete whenever H is a K2,3-free quadrangulation of the 2-sphere (equivalently, the plane) which is not a 4-cycle. From this result, we deduce an analogous statement for non-bipartite K2,3-free quadrangulations of the projective plane. This include several interesting classes of graphs, such as odd wheels, for which the complexity was known, and 4-chromatic generalized Mycielski graphs, for which it was not.
If we instead consider graphs G and H with loops on every vertex (i.e. reflexive graphs), then the reconfiguration problem is defined in a similar way except that a vertex can only change its colour to a neighbour of its current colour. In this setting, we use similar ideas to show that the reconfiguration problem for H-colourings is PSPACE-complete whenever H is a reflexive K4-free triangulation of the 2-sphere which is not a reflexive triangle. This proof applies more generally to reflexive graphs which, roughly speaking, resemble a triangulation locally around a particular vertex. This provides the first graphs for which H-Recolouring is known to be PSPACE-complete for reflexive instances.
| Item Type: | Journal Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Homomorphisms (Mathematics), Graph recolouring | |||||||||
| Journal or Publication Title: | European Journal of Combinatorics | |||||||||
| Publisher: | Academic Press | |||||||||
| ISSN: | 0195-6698 | |||||||||
| Official Date: | May 2020 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 86 | |||||||||
| Article Number: | 103086 | |||||||||
| DOI: | 10.1016/j.ejc.2020.103086 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||
| Date of first compliant deposit: | 22 January 2020 | |||||||||
| Date of first compliant Open Access: | 24 February 2021 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Related URLs: | ||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
