{
  "id": "2012.03210",
  "version": "v1",
  "published": "2020-12-06T08:09:33.000Z",
  "updated": "2020-12-06T08:09:33.000Z",
  "title": "Clique-chromatic number of dense random graphs",
  "authors": [
    "Yury Demidovich",
    "Maksim Zhukovskii"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The clique chromatic number of a graph is the minimum number of colors required to assign to its vertex set so that no inclusion maximal clique is monochromatic. McDiarmid, Mitsche and Pra\\l at proved that the clique chromatic number of the binomial random graph $G\\left(n,\\frac{1}{2}\\right) $ is at most $\\left(\\frac{1}{2}+o(1)\\right)\\log_2n$ with high probability. Alon and Krivelevich showed that it is greater than $\\frac{1}{2000}\\log_2n$ with high probability. In this paper we show that the upper bound is asymptotically tight.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-06T08:09:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C15"
    ],
    "keywords": [
      "dense random graphs",
      "clique-chromatic number",
      "clique chromatic number",
      "high probability",
      "binomial random graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}