Permanent problem IDPPL 068
Graph theory
The cochromatic number of G, denoted by ζ(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. Let χ(G) denote the chromatic number. If G is a random graph with n vertices and each edge included independently with probability 1/2 then is it true that almost surely χ(G) - ζ(G) → ∈fty as n→ ∈fty?
The cochromatic number of G, denoted by ζ(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. Let χ(G) denote the chromatic number. If G is a random graph with n vertices and each edge included independently with probability 1/2 then is it true that almost surely χ(G) - ζ(G) → ∈fty as n→ ∈fty?
A solution must appear in a reputable journal, with documentation that Erdős offered the displayed amount. Claims are administered by the Combinatorics Foundation; erdosproblems.com does not pay awards.