Constructing Tree Decompositions of Graphs with Bounded Gonality

05/12/2020
by   Hans L. Bodlaender, et al.
0

In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k, when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset