Odd properly colored cycles in edge-colored graphs. / Gutin, Gregory; Sheng, Bin; Wahlstrom, Magnus.

In: Discrete Mathematics, Vol. 340, No. 4, 04.2017, p. 817–821.

Research output: Contribution to journalArticle




It is well-known that an undirected graph has no odd cycle if and only if it is bipartite. A less obvious, but similar result holds for directed graphs: a strongly connected digraph has no odd cycle if and only if it is bipartite. Can this result be further generalized to more general graphs such as edge-colored graphs? In this paper, we study this problem and show how to decide if there exists an odd properly colored cycle in a given edge-colored graph. As a by-product, we show how to detect if there is a perfect matching in a graph with even (or odd) number of edges in a given edge set.
Original languageEnglish
Pages (from-to)817–821
Number of pages5
JournalDiscrete Mathematics
Issue number4
Early online date9 Dec 2016
Publication statusPublished - Apr 2017
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 27207575