On Supereulerian 2-Edge-Coloured Graphs

Jørgen Bang-Jensen*, Thomas Bellitto, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review


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.

Original languageEnglish
JournalGraphs and Combinatorics
Issue number6
Pages (from-to)2601-2620
Publication statusPublished - Nov 2021

Bibliographical note

Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.


  • 2-edge-coloured graph
  • Alternating cycle
  • Alternating hamiltonian cycle
  • Eulerian factor
  • Extension of a 2-edge-coloured graph
  • Supereulerian


Dive into the research topics of 'On Supereulerian 2-Edge-Coloured Graphs'. Together they form a unique fingerprint.

Cite this