论文标题
使用非亚洲群体切换$ m $ - 边缘色的图形
Switching $m$-edge-coloured graphs using non-Abelian groups
论文作者
论文摘要
令$ g $是一个图表，其边缘分别分配了$ M $ -Colours $ 1、2，\ ldots，m $，而让$γ$是$ s_m $的子组。根据$π$，在γ$中以$ x $的尊重$π\在γ$中的$π\在γ$中的$π\的操作缩小了边缘的颜色。当$γ$是Abelian时，有一个开发的转换理论。非亚伯群体众所周知。在本文中，我们考虑相对于包括对称，交替和二面基团在内的非亚伯群体进行切换。我们首先考虑是否使用$γ$的元素有一系列开关的问题，该元素将$ m $ edge的图形$ g $转换为$ m $ $ - 边缘彩色图$ h $。为每个要考虑的组给出了存在这种序列的必要条件。然后，我们考虑是否可以使用$γ$的元素切换$ M $ - 边缘彩色图，以便转换后的$ M $ - 边缘彩色图具有顶点$ k $颜色，还是对固定$ M $ $ - $ - $ - 边缘彩色图$ h $ h $的同构。对于刚才提到的群体，我们为这些决策问题的复杂性建立了二分法定理。这些是第一个用于着色或同构问题的二分法定理，并相对于$ s_2 $以外的任何组而切换。
Let $G$ be a graph whose edges are each assigned one of the $m$-colours $1, 2, \ldots, m$, and let $Γ$ be a subgroup of $S_m$. The operation of switching at a vertex $x$ with respect $π\in Γ$ permutes the colours of the edges incident with $x$ according to $π$. There is a well-developed theory of switching when $Γ$ 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 $Γ$ 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 $Γ$ 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$.
