Detecting a long even hole

Linda Cook; Paul Seymour

doi:10.1016/j.ejc.2022.103537

Detecting a long even hole

Linda Cook, Paul Seymour

Mathematics

Princeton University

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

Abstract

For each integer ℓ≥4, we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least ℓ and even.

Original language	American English
Article number	103537
Journal	European Journal of Combinatorics
Volume	104
DOIs	https://doi.org/10.1016/j.ejc.2022.103537
State	Published - Aug 2022

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2022.103537

Cite this

@article{aad01967123c41e4a9f499fa523e1c04,

title = "Detecting a long even hole",

abstract = "For each integer ℓ≥4, we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least ℓ and even.",

author = "Linda Cook and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier Ltd",

year = "2022",

month = aug,

doi = "10.1016/j.ejc.2022.103537",

language = "American English",

volume = "104",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Detecting a long even hole

AU - Cook, Linda

AU - Seymour, Paul

PY - 2022/8

Y1 - 2022/8

N2 - For each integer ℓ≥4, we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least ℓ and even.

AB - For each integer ℓ≥4, we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least ℓ and even.

UR - http://www.scopus.com/inward/record.url?scp=85130276672&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85130276672&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2022.103537

DO - 10.1016/j.ejc.2022.103537

M3 - Article

SN - 0195-6698

VL - 104

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103537

ER -

Detecting a long even hole

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this