Detecting a theta or a prism

Maria Chudnovsky, Rohan Kapadia

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

A theta in a graph is an induced subgraph consisting of two nonadjacent vertices joined by three disjoint paths. A prism in a graph is an induced subgraph consisting of two disjoint triangles joined by three disjoint paths. This paper gives a polynomial-time algorithm to test whether a graph has an induced subgraph that is either a prism or a theta.

Original languageEnglish (US)
Pages (from-to)1164-1186
Number of pages23
JournalSIAM Journal on Discrete Mathematics
Volume22
Issue number3
DOIs
StatePublished - 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • Detection algorithm
  • Induced subgraph
  • Prism
  • Theta

Fingerprint

Dive into the research topics of 'Detecting a theta or a prism'. Together they form a unique fingerprint.

Cite this