Recolouring reflexive digraphs |
| |
Authors: | Richard C. Brewster Jae-baek Lee Mark Siggers |
| |
Affiliation: | 1. Department of Mathematics and Statistics, Thompson Rivers University, Kamloops, BC, Canada;2. College of Natural Sciences, Kyungpook National University, Daegu 702-701, South Korea |
| |
Abstract: | Given digraphs and , the colouring graph has as its vertices all homomorphism of to . There is an arc between two homomorphisms if they differ on exactly one vertex , and if has a loop we also require . The recolouring problem asks if there is a path in between given homomorphisms and . We examine this problem in the case where is a digraph and is a reflexive, digraph cycle.We show that for a reflexive digraph cycle and a reflexive digraph , the problem of determining whether there is a path between two maps in can be solved in time polynomial in . When is not reflexive, we show the same except for certain digraph 4-cycles . |
| |
Keywords: | Homomorphisms Recolouring Reflexive digraphs Hom-graph |
本文献已被 ScienceDirect 等数据库收录! |
|