Detecting an induced net subdivision

Maria Chudnovsky; Paul Seymour; Nicolas Trotignon

doi:10.1016/j.jctb.2013.07.005

Detecting an induced net subdivision

Maria Chudnovsky
, Paul Seymour
, Nicolas Trotignon

Mathematics

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

7 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 language	English (US)
Pages (from-to)	630-641
Number of pages	12
Journal	Journal of Combinatorial Theory. Series B
Volume	103
Issue number	5
DOIs	https://doi.org/10.1016/j.jctb.2013.07.005
State	Published - Sep 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

Access to Document

10.1016/j.jctb.2013.07.005

Cite this

@article{0fb2a76a657b47f89e505de5a60c0db1,

title = "Detecting an induced net subdivision",

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.",

keywords = "Induced subgraph, Net, Polynomial-time algorithm, Subdivision",

author = "Maria Chudnovsky and Paul Seymour and Nicolas Trotignon",

year = "2013",

month = sep,

doi = "10.1016/j.jctb.2013.07.005",

language = "English (US)",

volume = "103",

pages = "630--641",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "5",

}

TY - JOUR

T1 - Detecting an induced net subdivision

AU - Chudnovsky, Maria

AU - Seymour, Paul

AU - Trotignon, Nicolas

PY - 2013/9

Y1 - 2013/9

N2 - 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.

AB - 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.

KW - Induced subgraph

KW - Net

KW - Polynomial-time algorithm

KW - Subdivision

UR - https://www.scopus.com/pages/publications/84883558803

UR - https://www.scopus.com/pages/publications/84883558803#tab=citedBy

U2 - 10.1016/j.jctb.2013.07.005

DO - 10.1016/j.jctb.2013.07.005

M3 - Article

AN - SCOPUS:84883558803

SN - 0095-8956

VL - 103

SP - 630

EP - 641

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 5

ER -

Detecting an induced net subdivision

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this