Showing 2025Show all
3 papers · 1 filter
math.CO2025
Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
Tala Eagling-Vose, Jorik Jooken, Felicia Lucke +2
We consider Colouring on graphs that are -subgraph-free for some fixed graph , which are graphs that do not contain as a subgraph. To classify the complexity of Colouring…
cs.CC2025
Restricted CSPs and F-free Digraph Algorithmics
Santiago Guzmán-Pro, Barnaby Martin
In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to -free and -subgraph-f…
math.CO2025
Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma +1
We continue the study of the recently-introduced C123-framework, for (simple) graph problems restricted to inputs specified by the forbidding of some finite set of subgraphs, to mo…