Abstract
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 language | English |
|---|---|
| Pages (from-to) | 817–821 |
| Number of pages | 5 |
| Journal | Discrete Mathematics |
| Volume | 340 |
| Issue number | 4 |
| Early online date | 9 Dec 2016 |
| DOIs | |
| Publication status | Published - Apr 2017 |