论文标题
超级2边彩色图
Supereulerian 2-edge-coloured graphs
论文作者
论文摘要
如果$ g $包含一个跨越的封闭步道，则2章彩色的图形$ g $是{\ bf supereulerian}，边缘在颜色上交替。一个2边彩的图的{\ bf eulerian因子}是顶点脱节引起的子图的集合，涵盖了$ g $的所有顶点，因此这些子图中的每一个都是supereulerian。我们给出一种多项式算法来测试2边彩的图是否具有欧拉因子并在存在时产生一个因子。如果它包含一对交替的$（u，v）$ - 路径（$（u，v）$ - trails），则2边彩色的图是{\ bf（trail-）颜色连接}，其工会是每对不同的不同的Vertices $ u，v $的交替封闭步行。如果$ xz $是$ g $的边缘，则每当$ g $的边缘与$ x $ u $连接到$ x $和$ z $，如果$ g $的边缘是$ g $的，则为2边彩色的图。 \ cite {balbuenadmtcs21}中引入的M封闭式2边彩色图，形成了对2边彩色完整图的丰富概括。我们表明，如果$ g $是M封闭式2边彩色完整图的延伸，那么$ G $是supereulerian的，并且仅当$ g $是与Trail-colour连接的，并且具有Eulerian因素。我们还表明，对于一般的2边色图，决定该图是否为supereulerian是NP的。最后，我们提出了许多开放问题。
A 2-edge-coloured graph $G$ is {\bf supereulerian} if $G$ contains a spanning closed trail in which the edges alternate in colours. An {\bf eulerian factor} of a 2-edge-coloured graph is a collection of vertex disjoint induced subgraphs which cover all the vertices of $G$ such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test if a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is {\bf (trail-)colour-connected} if it contains a pair of alternating $(u,v)$-paths ($(u,v)$-trails) whose union is an alternating closed walk for every pair of distinct vertices $u,v$. A 2-edge-coloured graph is {\bf M-closed} if $xz$ is an edge of $G$ whenever some vertex $u$ is joined to both $x$ and $z$ by edges of the same colour. M-closed 2-edge-coloured graphs, introduced in \cite{balbuenaDMTCS21}, form a rich generalization of 2-edge-coloured complete graphs. We show that if $G$ is an extension of an M-closed 2-edge-coloured complete graph, then $G$ is supereulerian if and only if $G$ is trail-colour-connected and has an eulerian factor. We also show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. Finally we pose a number of open problems.
