The cochromatic number of a finite simple
graph
is the smallest number of parts in a set partition
of its vertex set such that each part is a clique
or an independent vertex set (Lesniak-Foster
and Straight 1977, Erdős and Gimbel 1993). Such a set
partition is called a cocoloring. Throughout,
has at least one graph vertex.
Every proper vertex coloring is a cocoloring, and interchanging cliques and independent vertex sets gives a cocoloring of the graph complement. Consequently,
|
(1)
|
where
is the chromatic number. If
is the number of vertices,
is the independence number, and
is the clique number,
then
|
(2)
|
where
is the ceiling function, since no part can have
more than
vertices. A complete graph
or an empty graph has cochromatic number 1, and every
split graph has cochromatic number at most 2.
For the random graph , each possible graph
edge is included independently with probability
. The cochromatic and chromatic
numbers have the same leading asymptotic behavior,
|
(3)
|
with probability tending to 1 (Heckel 2025). Erdős and Gimbel (1993) asked whether nevertheless tends to infinity with probability
tending to 1. Heckel (2025) proved this for a phase-restricted set comprising roughly
95 percent of the integers
.
Petkov (2026) reports a full-sequence bound
|
(4)
|
where
|
(5)
|
The proof counts set partitions into classes of five consecutive sizes, each declared to be a clique
or an independent vertex set, and estimates
the overlaps between pairs of these set partitions.
The failure probabilities are summable, so the bound also holds almost
surely for every sufficiently large under any fixed joint distribution
of the graphs having these marginals.
Petkov (2026) gives a stronger phase-dependent coefficient determined by the fractional
part of the usual independence number
center, with a deterministic additive error of order
in the lower bound.
A matching upper bound at order
, conjectured by Heckel (2025), remains open.
The released Lean formalization verifies the full-sequence probability limit with the weaker coefficient
|
(6)
|
The stronger coefficient, phase-dependent refinement, and almost-sure conclusion are proved in the written argument but are outside the released theorem (Petkov 2026). Petkov (2026) reports mathematical assistance from GPT-5.6 Sol and Codex in proof development and Lean code, and automated Lean proof search and replay by Aristotle.