Open-access mathematical research insights
About Contact
Home / Erdos Problems / Problem #761

Problem #761: The cochromatic number of $G$, denoted by $\zeta(G)$, is...

The cochromatic number of $G$, denoted by $\zeta(G)$, is the minimum number of colours needed to colour the vertices of $G$ such that each colour...

Problem Statement

The cochromatic number of $G$, denoted by $\zeta(G)$, is the minimum number of colours needed to colour the vertices of $G$ such that each colour class induces either a complete graph or empty graph. The dichromatic number of $G$, denoted by $\delta(G)$, is the minimum number $k$ of colours required such that, in any orientation of the edges of $G$, there is a $k$-colouring of the vertices of $G$ such that there are no monochromatic oriented cycles.

Must a graph with large chromatic number have large dichromatic number? Must a graph with large cochromatic number contain a graph with large dichromatic number?
Categories: Graph Theory Chromatic Number

Progress

The first question is due to Erdős and Neumann-Lara. The second question is due to Erdős and Gimbel. A positive answer to the second question implies a positive answer to the first via the bound mentioned in [760].

Source: erdosproblems.com/761 | Last verified: January 16, 2026

Stay Updated

Get weekly digests of new research insights delivered to your inbox.