Outerplanar strongly perfect graph characterization

Informal Conjecture (outerplanar strongly perfect graphs) · arXiv:2003.01846

arXiv Informal medium confidence— first stated 2020-03-04

Authors: Maria Chudnovsky, Cemil Dibek, Paul Seymour

Status open high confidence

The informal conjecture suggests that the characterization of outerplanar strongly perfect graphs can be obtained from the minimal non-strongly-perfect examples constructed in the paper. No follow-up resolving or substantially advancing this specific question was found in the May 2026 review.

Reviewer notes. The complete final-page sentence was verified in the cached PDF; the earlier review incorrectly treated it as truncated.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. While obtaining a complete list of minimal non-strongly-perfect graphs appears to be out of reach, one might conjecture that the characterization of outerplanar strongly perfect graphs can be obtained through the minimal examples given in this paper.

Context

At the end of the paper the authors remark that a full characterisation of minimal non-strongly-perfect graphs is currently intractable, but suggest that restricting to the outerplanar setting may be a more approachable subproblem.

Notes. PDF source; the complete final-page sentence was verified in the cached paper.

Source paper

New Examples of Minimal Non-Strongly-Perfect Graphs
Maria Chudnovsky, Cemil Dibek, Paul Seymour · 2020-03-04
https://arxiv.org/abs/2003.01846 PDF source