Supereulerian 2-edge-coloured Graphs

by Anders Yeo

Abstract:

A 2-edge-coloured graph $G$ is supereulerian if $G$ contains a spanning closed trail in which the edges alternate in colours. 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. 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$ . In this talk we give a polynomial algorithms to test if a 2-edge-coloured graph has an eulerian factor and to test if it is trail-colour-connected.

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 [1], form a rich generalization of 2-edge-coloured complete graphs. We will discuss results on 2-edge-coloured M-closed graphs, complete bipartite graphs and complete multipartite graphs. In fact if $G$ is an extension of an M-closed 2-edge-coloured graph or if $G$ is a complete bipartite graph, then $G$ is supereulerian if and only if $G$ is trail-colour-connected and has an eulerian factor. The same result does not hold for semicomplete multipartite graphs.

We also show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian and finally we pose a number of open problems.

Joint work with Jørgen Bang-Jensen and Thomas Bellitto.

[1] A. Contreras-Balbuena, H. Galeana-Sánchez and I. A. Goldfeder, Alternating Hamiltonian cycles in 2-edge-colored multigraphs. Discrete Mathematics & Theoretical Computer Science, 21 (1), 2019

get slides

Event Timeslots (1)

Thursday
2:00 pm - 3:10 pm
Anders Yeo