To refer to this page use:
|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.|
|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|
|Pages:||630 - 641|
|Type of Material:||Journal Article|
|Journal/Proceeding Title:||JOURNAL OF COMBINATORIAL THEORY SERIES B|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.