Richard C Brewster ; Arnott Kidner ; Gary MacGillivray - The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial

dmtcs:9242 - Discrete Mathematics & Theoretical Computer Science, November 3, 2022, vol. 24, no 2 - https://doi.org/10.46298/dmtcs.9242
The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomialArticle

Authors: Richard C Brewster ; Arnott Kidner ; Gary MacGillivray

    A mixed graph is a set of vertices together with an edge set and an arc set. An $(m,n)$-mixed graph $G$ is a mixed graph whose edges are each assigned one of $m$ colours, and whose arcs are each assigned one of $n$ colours. A \emph{switch} at a vertex $v$ of $G$ permutes the edge colours, the arc colours, and the arc directions of edges and arcs incident with $v$. The group of all allowed switches is $\Gamma$. Let $k \geq 1$ be a fixed integer and $\Gamma$ a fixed permutation group. We consider the problem that takes as input an $(m,n)$-mixed graph $G$ and asks if there a sequence of switches at vertices of $G$ with respect to $\Gamma$ so that the resulting $(m,n)$-mixed graph admits a homomorphism to an $(m,n)$-mixed graph on $k$ vertices. Our main result establishes this problem can be solved in polynomial time for $k \leq 2$, and is NP-hard for $k \geq 3$. This provides a step towards a general dichotomy theorem for the $\Gamma$-switchable homomorphism decision problem.


    Volume: vol. 24, no 2
    Section: Graph Theory
    Published on: November 3, 2022
    Accepted on: August 31, 2022
    Submitted on: March 22, 2022
    Keywords: Mathematics - Combinatorics,05C15 (Primary) 68R10 (Secondary)
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    Consultation statistics

    This page has been seen 674 times.
    This article's PDF has been downloaded 469 times.