We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Detecting an induced subdivision of K 4

0
 Cite
 Share
 Related Material
 Download
 Purchase
No logo availableBanff International Research Station (BIRS) for Mathematical Innovation and Discovery
 Le, Ngoc Khang

Formal Metadata

Title
Detecting an induced subdivision of K 4
Title of Series
Number of Parts
24
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
We propose a polynomial-time algorithm to test whether a given graph contains a subdivision of \(K_4\) as an induced subgraph. This continues the study of detecting an induced subdivision of \(H\) for some fixed graph \(H\), which is still far from being complete. Our result answers a question posed by Chudnovsky et al. and Lévêque et al.
Keywords