The co-diameter-two co-chordal characterization conjecture

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.

Sources & referencesView supporting material

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.