Cover Image

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lozin, Vadim, Martin, Barnaby, Pandey, Sukanya, Paulusma, Daniel, Siggers, Mark, Smith, Siani, van Leeuwen, Erik Jan
Format:	Preprint
Published:	2022
Subjects:	Discrete Mathematics Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
by: Johnson, Matthew, et al.
Published: (2022)

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
by: Bok, Jan, et al.
Published: (2020)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

Steiner Forest for $H$-Subgraph-Free Graphs
by: Eagling-Vose, Tala, et al.
Published: (2026)

Colouring Probe $H$-Free Graphs
by: Paulusma, Daniël, et al.
Published: (2025)

Computing Subset Vertex Covers in $H$-Free Graphs
by: Brettell, Nick, et al.
Published: (2023)

The Complexity of Diameter on H-free graphs
by: Oostveen, Jelle J., et al.
Published: (2024)

The treewidth and pathwidth of graph unions
by: Alecu, Bogdan, et al.
Published: (2022)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
by: Lucke, Felicia, et al.
Published: (2024)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
by: Alecu, Bogdan, et al.
Published: (2024)

Forbidden Induced Subgraph Characterization of Word-Representable Split Graphs
by: Srinivasan, Eshwar, et al.
Published: (2025)

Forbidden Induced Subgraph Characterization of Word-Representable Co-bipartite Graphs
by: Srinivasan, Eshwar, et al.
Published: (2025)

Finding d-Cuts in Claw-free Graphs
by: Ahn, Jungho, et al.
Published: (2025)

Graph Classes Closed under Self-intersection
by: Dabrowski, Konrad K., et al.
Published: (2025)

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
by: Eagling-Vose, Tala, et al.
Published: (2025)

$k$-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for $k \geq 5$
by: la Tour, Max Dupré, et al.
Published: (2024)

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

Complexity of the Feedback Vertex Set Problem in Tournaments with Forbidden Subtournaments
by: Spirkl, Sophie, et al.
Published: (2026)

Functionality of box intersection graphs
by: Dallard, Clément, et al.
Published: (2023)

Reconfiguring Graph Homomorphisms on the Sphere
by: Lee, Jae-Baek, et al.
Published: (2018)

Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
by: Mählmann, Nikolas
Published: (2025)

Forbidden Patterns in Mixed Linear Layouts
by: Haun, Deborah, et al.
Published: (2024)

Subdivisions in dicritical digraphs with large order or digirth
by: Picasarri-Arrieta, Lucas, et al.
Published: (2024)

Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs
by: Goetze, Miriam, et al.
Published: (2024)

Path Eccentricity and Forbidden Induced Subgraphs
by: Cichacz, Sylwia, et al.
Published: (2025)

Comparing Width Parameters on Graph Classes
by: Brettell, Nick, et al.
Published: (2023)

Edge open packing: further characterizations
by: Pandey, Arti, et al.
Published: (2025)

Edge open packing on subclasses of chordal graphs
by: Santra, Kamal
Published: (2025)

Determining a graph from its reconfiguration graph
by: Berthe, Gaétan, et al.
Published: (2025)

Hitting all longest paths in $H$-free graphs and $H$-graphs
by: de Lima, Paloma T., et al.
Published: (2025)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
by: Lucke, Felicia, et al.
Published: (2023)

Vertex-edge domination on subclasses of bipartite graphs
by: Pandey, Arti, et al.
Published: (2025)

Edge densities of drawings of graphs with one forbidden cell
by: Hahn, Benedikt, et al.
Published: (2025)

Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials
by: Ai, Jiangdong, et al.
Published: (2024)

On Large Induced Outerplanar Subgraphs in $2$-Outerplanar Graphs
by: D'Elia, Marco, et al.
Published: (2026)

Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
by: Foucaud, Florent, et al.
Published: (2025)

Large Induced Subgraphs of Bounded Degree in Outerplanar and Planar Graphs
by: D'Elia, Marco, et al.
Published: (2024)

Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs
by: Dumitrescu, Adrian, et al.
Published: (2024)

EPPA numbers of graphs
by: Bradley-Williams, David, et al.
Published: (2023)

Forbidden induced subgraphs in iterative higher order line graphs
by: Sanghi, Aryan, et al.
Published: (2024)