Outerplanar strongly perfect graph characterization

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

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

Authors: Maria Chudnovsky, Cemil Dibek, Paul Seymour

Status open high confidence

The conjecture suggests that characterizing outerplanar strongly perfect graphs (equivalently, listing all minimal non-strongly-perfect outerplanar graphs) is a tractable subproblem, even though a full characterization of minimal non-strongly-perfect graphs appears out of reach. No follow-up paper resolving or making substantial progress on this specific conjecture was found in indexed literature through May 2026.

Reviewer notes. No follow-up paper addressing outerplanar strongly perfect graphs was found. The conjecture is informal (no precise statement is given in the truncated PDF source) and relatively recent (2020); absence of follow-up is consistent with it remaining open. The published journal version appeared in Discrete Mathematics (S0012365X21000479) but was behind a paywall and could not be fetched.

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 [statement truncated in PDF source].

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 extraction truncates the sentence at 'can be obtai'; the complete statement of the conjecture is not recoverable from the source. Confidence set to low due to truncation.

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