Constructing tree decompositions of graphs with bounded gonality

被引：0

作者：

Hans L. Bodlaender

Josse van Dobben de Bruyn

Dion Gijswijt

Harry Smit

机构：

[1] Utrecht University,Department of Information and Computing Sciences

[2] Delft University of Technology,Delft Institute of Applied Mathematics

[3] Max Planck Institute for Mathematics,undefined

来源：

Journal of Combinatorial Optimization | 2022年 / 44卷

关键词：

Tree decomposition; Gonality; Chip firing;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

页码：2681 / 2699

页数：18

共 28 条

[1]

Baker M(2008)Specialization of linear systems from curves to graphs Algebra Number Theory 2 613-653

[2]

Baker M(2007)Riemann–Roch and Abel–Jacobi theory on a finite graph Adv Math 215 766-788

[3]

Norine S(2009)Harmonic morphisms and hyperelliptic graphs Int Math Res Not 15 2914-2955

[4]

Baker M(2013)Chip-firing games, potential theory on graphs, and spanning trees J Comb Theory Ser B 120 164-182

[5]

Norine S(1998)A partial k-arboretum of graphs with bounded treewidth Theor Comput Sci 209 1-45

[6]

Baker M(2012)A tropical proof of the Brill–Noether theorem Adv Math 230 759-776

[7]

Shokrieh F(2015)A combinatorial Li–Yau inequality and rational points on curves Mathematische Annalen 361 211-258

[8]

Bodlaender HL(1990)The monadic second-order logic of graphs. I. Recognizable sets of finite graphs Inform Comput 85 12-75

[9]

Cools F(1990)Self-organized critical state of sandpile automaton models Phys Rev Lett 64 1613-953

[10]

Draisma J(2020)Treewidth is a lower bound on graph gonality Algebr Combin 3 941-149

← 1 2 3 →