Detecting an induced net subdivision
Author(s): Chudnovsky, Maria; Seymour, Paul D.; Trotignon, Nicolas
DownloadTo 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.