Detecting a Long Odd Hole

Maria Chudnovsky; Alex Scott; Paul Seymour

doi:10.1007/s00493-020-4301-z

Detecting a Long Odd Hole

Maria Chudnovsky, Alex Scott, Paul Seymour

Mathematics

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

6 Scopus citations

Abstract

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

Original language	English (US)
Journal	Combinatorica
Volume	41
Issue number	1
DOIs	https://doi.org/10.1007/s00493-020-4301-z
State	Published - Feb 2021

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-020-4301-z

Cite this

@article{8953a2213d444d5c88830d90fb89469d,

title = "Detecting a Long Odd Hole",

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

author = "Maria Chudnovsky and Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2021, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.",

year = "2021",

month = feb,

doi = "10.1007/s00493-020-4301-z",

language = "English (US)",

volume = "41",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}

TY - JOUR

T1 - Detecting a Long Odd Hole

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

PY - 2021/2

Y1 - 2021/2

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

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

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

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

U2 - 10.1007/s00493-020-4301-z

DO - 10.1007/s00493-020-4301-z

M3 - Article

AN - SCOPUS:85095492593

SN - 0209-9683

VL - 41

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -

Detecting a Long Odd Hole

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this