← All problems

Merino–Welsh conjecture for graphs

4 years old · traced to

Let GG be a connected graph without loops or bridges. Write τ(G)\tau(G) for the number of spanning trees of GG, b1(G)b1(G) for the number of acyclic orientations of GG, and b1∗(G)b1^*(G) for the number of totally cyclic orientations of GG.

Merino–Welsh conjecture. The inequality

max⁡(α(G),α∗(G))≥τ(G)\max(\alpha(G),\alpha^*(G))\geq\tau(G)

should hold.

The three quantities are evaluations of the Tutte polynomial: τ(G)=TG(1,1)\tau(G)=T_G(1,1), α(G)=TG(2,0)\alpha(G)=T_G(2,0), and α∗(G)=TG(0,2)\alpha^*(G)=T_G(0,2). The conjecture is known for several graph classes, including sparse or dense graphs, but is not resolved for all connected graphs without loops and bridges.

References

2 papers in this index state this conjecture (2010–2022). The statement above is taken from the most recent of them; the others are arXiv:1004.2639.

Source: https://arxiv.org/abs/2204.07132 Merino and Welsh (1999), original conjecture (cited in the source as Conjecture 7.1)

Source: Luis Ferroni and Benjamin Schröter, “The Merino–Welsh conjecture for split matroids”, arXiv:2204.07132 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.