TY - JOUR
T1 - Compatible spanning circuits in edge-colored graphs
AU - Guo, Zhiwei
AU - Li, Binlong
AU - Li, Xueliang
AU - Zhang, Shenggui
N1 - Springer deal
PY - 2020/7/1
Y1 - 2020/7/1
N2 - 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.
AB - 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.
KW - Edge-colored graph
KW - NP-complete problem
KW - Polynomial-time algorithm
KW - Compatible spanning circuit
KW - n/a OA procedure
UR - http://www.scopus.com/inward/record.url?scp=85090309395&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2020.111908
DO - 10.1016/j.disc.2020.111908
M3 - Article
VL - 343
JO - Discrete mathematics
JF - Discrete mathematics
SN - 0012-365X
IS - 7
M1 - 111908
ER -