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
| CREATOR | Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma, Siani Smith |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-07769