Maximum tight skew partitions in perfect graphs

Open Question on Number of Tight Skew Partitions · arXiv:1707.03747

arXiv Informal medium confidence— first stated 2017-07-12

Authors: Maria Chudnovsky, Aurélie Lagoutte, Paul Seymour, Sophie Spirkl

Status open high confidence

The paper establishes an upper bound of $n^3 \log n$ tight skew partitions in any $n$-vertex graph (improving the prior $n^4$ Kennedy--Reed bound), but the true maximum remains unknown. The authors observe they know of no graph with more than linearly many tight skew partitions, leaving open whether the correct order is $\Theta(n)$ or something between linear and $n^3 \log n$. A broad literature search spanning 2017--2026 found no follow-up paper resolving or improving this bound.

Reviewer notes. No follow-up found after five web calls. The open question asks for the true order of the maximum number of tight skew partitions in an $n$-vertex graph; the gap is between $\Omega(n)$ (no known super-linear example) and $O(n^3 \log n)$ (the paper's upper bound). The conjecture is closely related to the algorithmic complexity of finding balanced skew partitions in perfect graphs.

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

Informal. We do not know how many tight skew partitions there can really be; the authors do not know of a graph with more than linearly many tight skew partitions.

Context

The paper shows there are at most $n^3 \log n$ tight skew partitions in an $n$-vertex graph (improving the $n^4$ bound from the Kennedy–Reed list), because for every tight skew partition $(A,B)$ the set $B$ appears at least $k_2^2$ times in the Kennedy–Reed output, where $k_2$ is the size of the second-largest anticomponent of $G[B]$. The true maximum is unknown.

Notes. Stated as prose without a labelled theorem environment. PDF source.

Source paper

Colouring perfect graphs with bounded clique number
Maria Chudnovsky, Aurélie Lagoutte, Paul Seymour, Sophie Spirkl · 2017-07-12
https://arxiv.org/abs/1707.03747 PDF source