Katona–Varga's generalized Kriesell conjecture

Let t>0t>0, and let a minimally tt-tough graph be a tt-tough graph whose toughness decreases after deleting any edge. Katona–Varga's generalized conjecture. Every minimally tt-tough graph has a vertex of degree 2t\lceil 2t\rceil. The conjecture was disproved: Zheng and Sun (2024) found counterexamples for real tt close enough to 11, and Cheng, Li, and Liu (2024) later gave new families of 44-regular and 66-regular counterexamples.

Sources & referencesView supporting material

Primary source

Morteza Hasanvand, “On the existence of minimally tough graphs having large minimum degrees”, arXiv:2505.08131 (2025).

Additional references

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

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.