Abstract
A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. We show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. An 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 whether a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (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. We prove that a 2-edge-coloured complete bipartite graph is supereulerian if and only if it is colour-connected and has an eulerian factor. A 2-edge-coloured graph is 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 Contreras-Balbuena et al. (Discret Math Theoret Comput Sci 21:1, 2019), form a rich generalization of 2-edge-coloured complete graphs. We show that if G is obtained from an M-closed 2-edge-coloured graph H by substituting independent sets for the vertices of H, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. Finally we discuss 2-edge-coloured complete multipartite graphs and show that such a graph may not be supereulerian even if it is trail-colour-connected and has an eulerian factor.
| Originalsprog | Engelsk |
|---|---|
| Tidsskrift | Graphs and Combinatorics |
| Vol/bind | 37 |
| Udgave nummer | 6 |
| Sider (fra-til) | 2601-2620 |
| ISSN | 0911-0119 |
| DOI | |
| Status | Udgivet - nov. 2021 |
Bibliografisk note
Funding Information:The research was supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B. Part of this work was done while Bang-Jensen was on sabbatical at INRIA Sophia Antipolis. Hospitality and financial support is gratefully acknowledged. Ce travail a bénéficií d’une aide du gouvernement français, gérée par l’Agence Nationale de la Recherche au titre du projet Investissements d’Avenir UCAJEDI portant la référence no ANR-15-IDEX-01. This work was initiated while Bellitto was a postdoc at Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark. The author is also supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program Grant Agreement 714704. Yeo is also affiliated with Department of Pure and Applied Mathematics, University of Johannesburg, Auckland Park 2006 South Africa.
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.