2 papers
cs.DS2022
Computing Square Colorings on Bounded-Treewidth and Planar Graphs
Akanksha Agrawal, Dániel Marx, Daniel Neuen +1
A square coloring of a graph is a coloring of the square of , that is, a coloring of the vertices of such that any two vertices that are at distance at most in…
cs.DS2021
Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal
Karl Bringmann, Jasper Slusallek
The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph H is of bounded treewidth, as occurs in a variety…