Constructing Tree Decompositions of Graphs with Bounded Gonality

DOI10.1007/978-3-030-58150-3_31MaRDI QIDQ6340518arXivFDO

Authors Hans L. Bodlaender, Josse van Dobben de Bruyn, Dion Gijswijt, Harry Smit

Publication date 12 May 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-58150-3_31

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

arXiv classification

cs.DM math.CO

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.

This page was built for publication: Constructing Tree Decompositions of Graphs with Bounded Gonality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340518)