Odd properly colored cycles in edge-colored graphs

Gregory Gutin; Bin Sheng; Magnus Wahlstrom

doi:10.1016/j.disc.2016.11.017

Odd properly colored cycles in edge-colored graphs

Research output: Contribution to journal › Article › peer-review

250 Downloads (Pure)

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	https://doi.org/10.1016/j.disc.2016.11.017
Publication status	Published - Apr 2017

Access to Document

10.1016/j.disc.2016.11.017

Accepted ManuscriptAccepted author manuscript, 227 KBLicence: CC BY-NC-ND

Cite this

@article{85b666c28959490ba358e961e587d70a,

title = "Odd properly colored cycles in edge-colored graphs",

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.",

author = "Gregory Gutin and Bin Sheng and Magnus Wahlstrom",

year = "2017",

month = apr,

doi = "10.1016/j.disc.2016.11.017",

language = "English",

volume = "340",

pages = "817–821",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Odd properly colored cycles in edge-colored graphs

AU - Gutin, Gregory

AU - Sheng, Bin

AU - Wahlstrom, Magnus

PY - 2017/4

Y1 - 2017/4

N2 - 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.

AB - 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.

U2 - 10.1016/j.disc.2016.11.017

DO - 10.1016/j.disc.2016.11.017

M3 - Article

SN - 0012-365X

VL - 340

SP - 817

EP - 821

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 4

ER -