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
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/13337 |
| Date | 31 August 2021 |
| Creators | Kidner, Arnott |
| Contributors | MacGillivray, Gary, Brewster, Richard Charles |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.0025 seconds