Return to search

Gamma-Switchable 2-Colourings of (m,n)-Mixed Graphs

A $(m,n)$-mixed graph is a mixed graph whose edges are assigned one of $m$ colours, and whose arcs are assigned one of $n$ colours. Let $G$ be a $(m,n)$-mixed graph and $\pi=(\alpha,\beta,\gamma_1,\gamma_2,\ldots,\gamma_n)$ be a $(n+2)$-tuple of permutations from $S_m \times S_n \times S_2^n$. We define \emph{switching at a vertex $v$ with respect to $\pi$} as follows. Replace each edge $vw$ of colour $\phi$ by an edge $vw$ of colour $\alpha(\phi)$, and each arc $vx$ of colour $\phi$ by an arc $\gamma_\phi(vx)$ of colour $\beta(\phi)$.

In this thesis, we study the complexity of the question: ``Given a $(m,n)$-mixed graph $G$, is there a sequence of switches at vertices of $G$ with respect to the fixed group $\Gamma$ so that the resulting $(m,n)$-mixed graph admits a homomorphism to some $(m,n)$-mixed graph on $2$ vertices?''

We show the following: (1) When restricted to $(m,0)$-mixed graphs $H$ on at most $2$ vertices, the $\Gamma$-switchable homomorphism decision problem is solvable in polynomial time; (2) for each bipartite $(0,n)$-mixed graph $H$, there is a bipartite $(2n,0)$-mixed graph such that the respective $\Gamma$-switchable homomorphism decision problems are polynomially equivalent; (3) For all $(m,n)$-mixed graphs and groups, when $H$ has at most $2$ vertices, the $\Gamma$-switchable homomorphism decision problem is polynomial time solvable; (4) For a yes-instance of the $\Gamma$-switchable homomorphism problem for $(m,0)$-mixed graphs, we can find in quadratic time a sequence of switches on $G$ such that the resulting $(m,0)$-mixed graph admits a homomorphism to $H$.

By proving (1)-(4), we show that the $\Gamma$-switchable $2$-colouring problem for $(m,n)$-mixed graphs is solvable in polynomial time for all finite permutation groups $\Gamma$ and provide a step towards a dichotomy theorem for the complexity of the $\Gamma$-switchable homomorphism decision problem. / Graduate

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/13337
Date31 August 2021
CreatorsKidner, Arnott
ContributorsMacGillivray, Gary, Brewster, Richard Charles
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
Formatapplication/pdf
RightsAvailable to the World Wide Web

Page generated in 0.0019 seconds