TOPICS
Search

Cochromatic Number


The cochromatic number zeta(G) of a finite simple graph G 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, G 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,

 zeta(G)=zeta(G^_)<=min{chi(G),chi(G^_)},
(1)

where chi(G) is the chromatic number. If n is the number of vertices, alpha(G) is the independence number, and omega(G) is the clique number, then

 zeta(G)>=[n/(max{alpha(G),omega(G)})],
(2)

where [x] is the ceiling function, since no part can have more than max{alpha(G),omega(G)} 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 G_n∼G(n,1/2), each possible graph edge is included independently with probability 1/2. The cochromatic and chromatic numbers have the same leading asymptotic behavior,

 zeta(G_n)∼chi(G_n)∼n/(2log_2n),
(3)

with probability tending to 1 (Heckel 2025). Erdős and Gimbel (1993) asked whether chi(G_n)-zeta(G_n) 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 n.

Petkov (2026) reports a full-sequence bound

 Pr(chi(G_n)-zeta(G_n)>=c_0n/((lnn)^3))->1,
(4)

where

 c_0=((ln2)^2)/4ln(169)/(100)=0.0630268508....
(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 n 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 nlnlnn/(lnn)^4 in the lower bound. A matching upper bound at order n/(lnn)^3, conjectured by Heckel (2025), remains open.

The released Lean formalization verifies the full-sequence probability limit with the weaker coefficient

 c_(Lean)=((ln2)^2)/4ln(200)/(153)=0.0321758716....
(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.


See also

Chromatic Number, Clique, Graph Complement, Independent Vertex Set, Random Graph

Explore with Wolfram|Alpha

References

Erdős, P. and Gimbel, J. "Some Problems and Results in Cochromatic Theory." In Quo Vadis, Graph Theory? A Source Book for Challenges and Directions (Ed. J. Gimbel, J. W. Kennedy, and L. V. Quintas). Amsterdam, Netherlands: North-Holland, pp. 261-264, 1993. https://doi.org/10.1016/S0167-5060(08)70393-5.Heckel, A. "The Difference Between the Chromatic and the Cochromatic Number of a Random Graph." 19 Feb 2025. https://arxiv.org/abs/2409.17614v2.Lesniak-Foster, L. and Straight, H. J. "The Cochromatic Number of a Graph." Ars Combin. 3, 39-45, 1977. https://combinatorialpress.com/ars/vol3/.Petkov, S. "A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph." 15 Nov 2026. https://arxiv.org/abs/2608.30604v2.

Cite this as:

Weisstein, Eric W. "Cochromatic Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CochromaticNumber.html

Subject classifications