Upper bound on the divisorial gonality of a graph

$$\rm{gon}(G) \leq \frac{|E(G)|-|V(G)|}{2} + 2$$ , where $$\rm{gon}(G)$$ the denotes the divisorial gonality of graph $$G$$ .

Remarks

• It is a conjecture of Matthew Baker based on extensive computer calculations by Adam Tart .
• In the context of graph divisor theory $$|E(G)|-|V(G)|+ 1$$ is called as the genus of the graph and denoted by $$g$$ . Using this notion, the conjecture can be formulated as $$\rm{gon}(G) \leq \lfloor \frac{g+3}{2} \rfloor$$ , which is the original form of the conjecture, see Conj. 3.10. in .
• It is also conjectured in that for each integer $$g \geq 0$$ , there exists a graph of genus $$g$$ with gonality exactly $$\lfloor \frac{g+3}{2} \rfloor$$ .
• There is also a more general version of the conjecture in , the so-called Brill-Noether Conjecture for Graphs: Fix integers $$g, r, d \geq 0$$ , and set $$\varrho(g, r, d) = g − (r + 1)(g − d + r)$$ . Then:
  • (1) If $$\varrho(g, r, d) \geq 0$$ , then every graph of genus $$g$$ has a divisor $$D$$ with $$\rm{rank}(D) = r$$ and $$\deg(D) \leq d$$ .
  • (2) If $$\varrho(g, r, d) \lt 0$$ , then there exists a graph of genus $$g$$ for which there is no divisor D with $$\rm{rank}(D) = r$$ and $$\deg(D) \leq d$$ .