Detecting an induced net subdivision

Maria Chudnovsky, Paul Seymour, Nicolas Trotignon

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

A net is a graph consisting of a triangle C and three more vertices, each of degree one and with its neighbour in C, and all adjacent to different vertices of C. We give a polynomial-time algorithm to test whether an input graph has an induced subgraph which is a subdivision of a net. Unlike many similar questions, this does not seem to be solvable by an application of the "three-in-a-tree" subroutine.

Original languageEnglish (US)
Pages (from-to)630-641
Number of pages12
JournalJournal of Combinatorial Theory. Series B
Volume103
Issue number5
DOIs
StatePublished - Sep 1 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Induced subgraph
  • Net
  • Polynomial-time algorithm
  • Subdivision

Fingerprint Dive into the research topics of 'Detecting an induced net subdivision'. Together they form a unique fingerprint.

Cite this