Constructing tree decompositions of graphs with bounded gonality

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 al...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2022-11, Vol.44 (4), p.2681-2699
Main Authors: Bodlaender, Hans L., van Dobben de Bruyn, Josse, Gijswijt, Dion, Smit, Harry
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Combinatorics
Convex and Discrete Geometry
Decomposition
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Polynomials
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1382-6905
1573-2886
DOI:10.1007/s10878-021-00762-w