Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 761

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?

Status. Open.

Source. erdosproblems.com/761, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #761, https://www.erdosproblems.com/761.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (4)

Graph Coloring graph_coloring/mohar_2015_dichromatic_number_fractional_chromatic_number Theorem 1.3 (p. 2): fractional chromatic number at least t forces fractional dichromatic number at least t/(4 log_2(2et^2))Theorem 3.5 (p. 10): the dichromatic number of KG(n,k) is at least floor((n-2k+2)/(8 log_2(n/k)))

Graph