Switching m-edge-coloured graphs using non-Abelian groups

arXiv2207.12528MaRDI QIDQ6406033FDOQ6406033

Authors: Chris Duffy, Gary MacGillivray, Ben Tremblay 

Publication date: 25 July 2022

Abstract: Let $G$ be a graph whose edges are each assigned one of the $m$-colours $1,2,ldots,m$, and let $Gamma$ be a subgroup of $S_m$. The operation of switching at a vertex $x$ with respect $piinGamma$ permutes the colours of the edges incident with $x$ according to $pi$. There is a well-developed theory of switching when $Gamma$ is Abelian. Much less is known for non-Abelian groups. In this paper we consider switching with respect to non-Abelian groups including symmetric, alternating and dihedral groups. We first consider the question of whether there is a sequence of switches using elements of $Gamma$ that transforms an $m$-edge-coloured graph $G$ to an $m$-edge coloured graph $H$. Necessary and sufficient conditions for the existence of such a sequence are given for each of the groups being considered. We then consider the question of whether an $m$-edge coloured graph can be switched using elements of $Gamma$ so that the transformed $m$-edge coloured graph has a vertex $k$-colouring, or a homomorphism to a fixed $m$-edge coloured graph $H$. For the groups just mentioned we establish dichotomy theorems for the complexity of these decision problems. These are the first dichotomy theorems to be established for colouring or homomorphism problems and switching with respect to any group other than $S_2$.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Switching $m$-edge-coloured graphs using non-Abelian groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6406033)