Constructing Tree Decompositions of Graphs with Bounded Gonality
Publication date
2020
Authors
Bodlaender, Hans
Bruyn, Josse van Dobben de
Gijswijt, Dion
Smit, Harry
Editors
Kim, Donghyun
Uma, R. N.
Cai, Zhipeng
Lee, Dong Hoon
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
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.
Keywords
Taverne
Citation
Bodlaender, H L, Bruyn, J V D D, Gijswijt, D & Smit, H 2020, Constructing Tree Decompositions of Graphs with Bounded Gonality. in D Kim, R N Uma, Z Cai & D H Lee (eds), Computing and Combinatorics : 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020, Proceedings. Lecture Notes in Computer Science , vol. 12273, Springer, Cham, pp. 384-396. https://doi.org/10.1007/978-3-030-58150-3_31