The co-diameter-two co-chordal characterization conjecture

Less than 1 year old · traced to

Let GG be a co-chordal graph, meaning that its complement is chordal, and suppose that the co-diameter of GG, namely the diameter of its complement, is 22. A graph is non-trivially minimally tough if it is minimally tough and not complete. For ℓ≥1\ell\geq 1, let Sℓ,ℓ,ℓS_{\ell,\ell,\ell} be obtained from three disjoint stars K1,ℓK_{1,\ell} by adding a triangle between their centers.

Co-diameter-two characterization conjecture. The graph GG is non-trivially minimally tough if and only if GG is isomorphic to Sℓ,ℓ,ℓS_{\ell,\ell,\ell} for some ℓ≥1\ell\geq 1.

This is the formal version of the preceding conjectural description of the unresolved co-diameter-22 case for co-chordal graphs, and remains open.

References

Primary source

J. Pascal Gollin, Martin Milanič and Laura Ogrin, “Minimal toughness in subclasses of weakly chordal graphs”, arXiv:2603.05100 (2026).

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.