Changes

'''Conjecture''' The gonality of any graph <math>G</math> is at most <math>\frac{|E(G)|-|V(G)|}{2} + 2 </math>.

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

Based on extensive computer calculations by Adam Tart (an undergraduate at Georgia<references>Tech)<ref name="B08">M. Baker, we conjecture that similar results hold in the purely combinatorial setting ''Specialization of finitelinear systems from curves to graphs:Conjecture 3.9 (Brill-Noether Conjecture for Graphs). Fix integers g, r, d ≥ 0'', Algebra and setρNumber Theory (g, r, d2008) [http://citeseerx.ist.psu.edu/viewdoc/summary?doi= g − (r + 10.1)(g − d + r). Then:(1) If ρ(g, r, d) ≥ 0, then every graph of genus g has a divisor D with r(D) = r anddeg(D) ≤ d.SPECIALIZATION OF LINEAR SYSTEMS13(2) If ρ(g, r, d) < 0, there exists a graph of genus g for which there is no divisor D withr(D) = r and deg(D) ≤ d240.In the special case r = 16689 DOI link], Conjecture 3.9 can be reformulated as follows[http:Conjecture 3//people.10 (Gonality Conjecture for Graphs)math. For each integer g ≥ 0:(1) The gonality of any graph of genus g is at most b(g + 3)gatech.edu/~mbaker/pdf/2cspecialization.pdf Author Link]</ref>(2) There exists a graph of genus g with gonality exactly b(g + 3)</2c.references>Adam Tart has verified part (2) of Conjecture 3.10 for g ≤ 12, and part (2) of Conjec[[Category:Chip-firing]]ture 3.9 for 2 ≤ r ≤ 4 and g ≤ 10. He has also verified that part (1) of Conjecture 3.10 holdsfor approximately 1000 randomly generated graphs of genus at most 10, and has similarlyverified part (1) of Conjecture 3.9 for around 100 graphs in the case 2 ≤ r ≤ 4.[[Category:Open Problems]]