erdős #761
The cochromatic number of , denoted by , is the minimum number of colours needed to colour the vertices of such that each colour class induces either a complete graph or empty graph. The dichromatic number of , denoted by , is the minimum number of colours required such that, in any orientation of the edges of , there is a -colouring of the vertices of 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?
Worked, still open.
graph theory · open · 0 attempts
use this record
vela registry pull vfr_37aec80d874a0239vela reproduce examples/erdos-problemsevidence
unverified AI candidates (2)
gpt-erdos · GPT-5.2 Pro + Deep Research · unverified
Write (\vec\chi(D)) for the usual **dichromatic number of a digraph** $D$: the minimum number of colours needed so that each colour class induces an **acyclic** digraph. Your (\delta(G)) for an undirected graph $G$ is exactly [ \delta(G)=\max{\vec\chi(D): D \text{ is an orientation of }G}, ] i.e. the **maximum** dichro…
candidate solution ↗llm-hunter · gpt pro 5.2 · unverified
1 LLM attack(s) recorded (gpt pro 5.2); unverified.
candidate solution ↗links
Create a formalisation here · link
status
open