Complexity Framework for Forbidden Subgraphs II: When Hardness Is Not Preserved under Edge Subdivision

Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Type: Preprint

Publication Date: 2022-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2211.14214

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Complexity Framework For Forbidden Subgraphs I: The Framework	2022	Matthew Johnson Barnaby Martin Jelle J. Oostveen Sukanya Pandey Daniël Paulusma Siani Smith Erik Jan van Leeuwen
+	Complexity Framework for Forbidden Subgraphs I: The Framework	2025	Matthew Johnson Barnaby Martin Jelle J. Oostveen Sukanya Pandey Daniël Paulusma Siani Smith Erik Jan van Leeuwen
+	Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs	2023	Matthew Johnson Barnaby Martin Sukanya Pandey Daniël Paulusma Siani Smith Erik Jan van Leeuwen
+	Complexity of $C_k$-coloring in hereditary classes of graphs	2020	Maria Chudnovsky Shenwei Huang Paweł Rzążewski Sophie Spirkl Mingxian Zhong
+ PDF Chat	Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs	2015	Konrad K. Dabrowski Daniël Paulusma
+ PDF Chat	Complexity of C-coloring in hereditary classes of graphs	2023	Maria Chudnovsky Shenwei Huang Paweł Rzążewski Sophie Spirkl Mingxian Zhong
+	Hardness of approximation for H-free edge modification problems	2016	Ivan Bliznets Marek Cygan Paweł Komosa Michał Pilipczuk
+	Hardness of approximation for H-free edge modification problems	2016	Ivan Bliznets Marek Cygan Paweł Komosa Michał Pilipczuk
+	Induced Minor Free Graphs: Isomorphism and Clique-width	2016	Rémy Belmonte Yota Otachi Pascal Schweitzer
+	Induced Minor Free Graphs: Isomorphism and Clique-width	2016	Rémy Belmonte Yota Otachi Pascal Schweitzer
+	Colouring Square-Free Graphs without Long Induced Paths	2018	Serge Gaspers Shenwei Huang Daniël Paulusma
+	Colouring Square-Free Graphs without Long Induced Paths	2018	Serge Gaspers Shenwei Huang Daniël Paulusma
+	Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs	2014	Konrad K. Dabrowski Daniël Paulusma
+	Induced subgraphs and path decompositions	2022	Robert Hickingbotham
+ PDF Chat	Induced Subgraphs and Path Decompositions	2023	Robert Hickingbotham
+	Treewidth versus clique number in graph classes with a forbidden structure	2020	Clément Dallard Martin Milanič Kenny Štorgel
+	Few Induced Disjoint Paths for $H$-Free Graphs	2022	Barnaby Martin Daniël Paulusma Siani Smith Erik Jan van Leeuwen
+	Hardness of Approximation for H-Free Edge Modification Problems	2016	Ivan Bliznets Marek Cygan Paweł Komosa Michał Pilipczuk
+ PDF Chat	Few Induced Disjoint Paths for H-Free Graphs	2022	Barnaby Martin Daniël Paulusma Siani Smith Erik Jan van Leeuwen
+	Perfect matching cuts partitioning a graph into complementary subgraphs	2022	Diane Castonguay Erika M. M. Coelho Hebert Coelho Julliano R. Nascimento Uéverton S. Souza

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors