Constructing tree decompositions of graphs with bounded gonality

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

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

2 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication26th International Conference, COCOON 2020, Proceedings
EditorsDonghyun Kim, R.N. Uma, Zhipeng Cai, Dong Hoon Lee
Place of PublicationCham
PublisherSpringer
Pages384-396
Number of pages13
ISBN (Electronic)978-3-030-58150-3
ISBN (Print)978-3-030-58149-7
DOIs
Publication statusPublished - 2020
Event26th International Conference on Computing and Combinatorics, COCOON 2020 - Atlanta, United States
Duration: 29 Aug 202031 Aug 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume12273
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on Computing and Combinatorics, COCOON 2020
CountryUnited States
CityAtlanta
Period29/08/2031/08/20

Fingerprint Dive into the research topics of 'Constructing tree decompositions of graphs with bounded gonality'. Together they form a unique fingerprint.

Cite this