Complexity framework for forbidden subgraphs II: edge subdivision and the “H”-graphs

For a fixed set H of graphs, a graph G is H-subgraph-free if G does not contain any H ∈ H as a (not necessarily induced) subgraph. A recent framework gives a complete classification on H-subgraph-free graphs (for finite sets H) for problems that are solvable in polynomial time on graph classes of bo...

Full description

Saved in:
Bibliographic Details
Main Authors: Vadim Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark Siggers, Siani Smith, Erik Jan van Leeuwen
Format: Default Conference proceeding
Published: 2024
Subjects:
Information and computing sciences
Forbidden subgraph
Complexity dichotomy
Edge subdivision
Treewidth
Online Access:https://hdl.handle.net/2134/28429262.v1
Tags: Add Tag
No Tags, Be the first to tag this record!

Similar Items