Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs

Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma, Siani Smith · 2025

Read Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs by Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma, Siani Smith (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-07769.txt.

Description

Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma, and Siani Smith pushed a complexity frame past plain graphs. Their paper, from twenty twenty-five, is the fifth in a series. The frame sorts graph tasks by which subgraphs are banned from the input. Past parts dealt with simple graphs only. This part lets graphs hold multi edges and loops at a vertex.

They study three cut tasks in this wider world, plus families of map tasks onto small graphs. With a single banned subgraph, the first three tasks act like the plain case. With sets of banned parts, the sorting starts to split away. Readers in graph theory get a wider map of where hard tasks turn easy.

Catalog record

CREATORTala Eagling-Vose, Barnaby Martin, Daniel Paulusma, Siani Smith
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-07769

Browse the full library · About the Tower of Babel