Skip to main content

Detecting an induced net subdivision

Author(s): Chudnovsky, Maria; Seymour, Paul D; Trotignon, Nicolas

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1x96x
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. (C) 2013 Elsevier Inc. All rights reserved.
Publication Date: Sep-2013
Electronic Publication Date: 23-Aug-2013
Citation: Chudnovsky, Maria, Seymour, Paul, Trotignon, Nicolas. (2013). Detecting an induced net subdivision. JOURNAL OF COMBINATORIAL THEORY SERIES B, 103 (630 - 641. doi:10.1016/j.jctb.2013.07.005
DOI: doi:10.1016/j.jctb.2013.07.005
ISSN: 0095-8956
Pages: 630 - 641
Type of Material: Journal Article
Journal/Proceeding Title: JOURNAL OF COMBINATORIAL THEORY SERIES B
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.