Back to Search
Start Over
Constructing Tree Decompositions of Graphs with Bounded Gonality
- Publication Year :
- 2020
-
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.<br />Comment: 18 pages, 3 figures
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2005.05569
- Document Type :
- Working Paper