The co-diameter-two co-chordal characterization conjecture
The co-diameter-two co-chordal characterization conjecture
Let be a co-chordal graph, meaning that its complement is chordal, and suppose that the co-diameter of , namely the diameter of its complement, is . A graph is non-trivially minimally tough if it is minimally tough and not complete. For , let be obtained from three disjoint stars by adding a triangle between their centers.
Co-diameter-two characterization conjecture. The graph is non-trivially minimally tough if and only if is isomorphic to for some .
This is the formal version of the preceding conjectural description of the unresolved co-diameter- 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.