Generalized Kriesell's conjecture for minimally tough graphs

Let tt be a real number, and let GG be a graph. A graph is minimally tt-tough when τ(G)=t\tau(G)=t and τ(Ge)<t\tau(G-e)<t for every edge eE(G)e\in E(G), where τ(G)\tau(G) denotes its toughness. It is Generalized Kriesell's conjecture that every minimally tt-tough graph has a vertex of degree 2t\lceil 2t\rceil. This naturally generalizes Kriesell's conjecture for t=1t=1, and the paper reports that the associated Kriesell conjecture was recently disproved.

Sources & referencesView supporting material

Primary source

Gyula Y. Katona and Humara Khan, “Minimally tough series-parallel graphs with toughness at least 1/2”, arXiv:2512.01905 (2025).

Additional references

4 papers in this index state this conjecture (2018–2025). The statement above is taken from the most recent of them; the others are arXiv:2311.08634, arXiv:2209.00376, arXiv:1802.00055.

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.