Detecting an Odd Hole

Abstract

We give a polynomial-time algorithm to test whether a graph contains an induced cycle with length more than three and odd.

Document Details

• Document Type: Pub Defense Publication
• Publication Date: Jan 29, 2020
• Source ID: 10.1145/3375720

Entities

People

• Alex Scott
• Maria Chudnovsky
• Paul Seymour
• Sophie Spirkl

Organizations

• Air Force Office of Scientific Research
• Army Research Office
• National Science Foundation
• Princeton University
• Rutgers University
• University of Oxford