Constructing tree decompositions of graphs with bounded gonality

Conference Paper (2020)
Author(s)

Hans L. Bodlaender (Universiteit Utrecht)

Josse van Dobben de Bruyn (TU Delft - Discrete Mathematics and Optimization)

D.C. Gijswijt (TU Delft - Discrete Mathematics and Optimization)

Harry Smit (Universiteit Utrecht)

Research Group
Discrete Mathematics and Optimization
Copyright
© 2020 Hans L. Bodlaender, J. van Dobben de Bruyn, Dion Gijswijt, Harry Smit
DOI related publication
https://doi.org/10.1007/978-3-030-58150-3_31
More Info
expand_more
Publication Year
2020
Language
English
Copyright
© 2020 Hans L. Bodlaender, J. van Dobben de Bruyn, Dion Gijswijt, Harry Smit
Research Group
Discrete Mathematics and Optimization
Bibliographical Note
Accepted author manuscript@en
Pages (from-to)
384-396
ISBN (print)
978-3-030-58149-7
ISBN (electronic)
978-3-030-58150-3
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

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.

Files

License info not available