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
 Zitieren
 Teilen
 Zugehöriges Material
 Herunterladen
 Bestellen
Kein Logo verfügbarBanff International Research Station (BIRS) for Mathematical Innovation and Discovery
 Le, Ngoc Khang

Formale Metadaten

Titel
Detecting an induced subdivision of K 4
Serientitel
Anzahl der Teile
24
Autor
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
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.
Schlagwörter