Constructing tree decompositions of graphs with bounded gonality

Conference paper (2020)

Authors

Hans L. Bodlaender Universiteit Utrecht

J. van Dobben de Bruyn Discrete Mathematics and Optimization -

Dion Gijswijt Discrete Mathematics and Optimization -

Harry Smit Universiteit Utrecht

Research Group

Discrete Mathematics and Optimization () (TU Delft)

DOI: https://doi.org/10.1007/978-3-030-58150-3_31

To reference this document use:

http://resolver.tudelft.nl/uuid:8a8ff540-209f-477a-b849-0e5dc402fa33

More Info

expand_more

Published Date

2020

Language

English

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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

Main_conference_version_for_pu... (pdf)

(pdf | 0.518 Mb)

Unknown license

Bodlaender2020_Chapter_Constru... (pdf)

(pdf | 0.43 Mb)

Unknown license

Download not available