Odd holes in bull-free graphs

Maria Chudnovsky, Vaidy Sivaraman

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this test can be done in polynomial time if the input graph has no induced subgraph isomorphic to the bull (a triangle with two disjoint pendant edges).

Original languageEnglish (US)
Pages (from-to)951-955
Number of pages5
JournalSIAM Journal on Discrete Mathematics
Volume32
Issue number2
DOIs
StatePublished - 2018

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • Algorithm
  • Bull-free
  • Odd hole

Fingerprint

Dive into the research topics of 'Odd holes in bull-free graphs'. Together they form a unique fingerprint.

Cite this