Compatible spanning circuits in edge-colored graphs

Zhiwei Guo, Binlong Li, Xueliang Li, Shenggui Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

A compatible spanning circuit in a (not necessarily properly) edge-colored graph G is a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. Sufficient conditions for the existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and Euler tours), and polynomial-time algorithms for finding compatible Euler tours have been considered in previous literature. More recently, sufficient conditions for the existence of more general compatible spanning circuits in specific edge-colored graphs have been established. In this paper, we consider the existence of (more general) compatible spanning circuits from an algorithmic perspective. We first show that determining whether an edge-colored connected graph contains a compatible spanning circuit is an NP-complete problem. Next, we describe two polynomial-time algorithms for finding compatible spanning circuits in edge-colored complete graphs. These results in some sense give partial support to a conjecture on the existence of compatible Hamilton cycles in edge-colored complete graphs due to Bollobás and Erdős from the 1970s.

Original languageEnglish
Article number111908
JournalDiscrete mathematics
Volume343
Issue number7
DOIs
Publication statusPublished - 1 Jul 2020

Keywords

  • UT-Hybrid-D
  • Edge-colored graph
  • NP-complete problem
  • Polynomial-time algorithm
  • Compatible spanning circuit

Fingerprint Dive into the research topics of 'Compatible spanning circuits in edge-colored graphs'. Together they form a unique fingerprint.

Cite this