{
  "id": "2104.00412",
  "version": "v1",
  "published": "2021-04-01T11:48:14.000Z",
  "updated": "2021-04-01T11:48:14.000Z",
  "title": "Uncountably many minimal hereditary classes of graphs of unbounded clique-width",
  "authors": [
    "Robert Brignall",
    "Daniel Cocks"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given an infinite word over the alphabet $\\{0,1,2,3\\}$, we define a class of bipartite hereditary graphs $\\mathcal{G}^\\alpha$, and show that $\\mathcal{G}^\\alpha$ has unbounded clique-width unless $\\alpha$ contains at most finitely many non-zero letters. We also show that $\\mathcal{G}^\\alpha$ is minimal of unbounded clique-width if and only if $\\alpha$ belongs to a precisely defined collection of words $\\Gamma$. The set $\\Gamma$ includes all almost periodic words containing at least one non-zero letter, which both enables us to exhibit uncountably many pairwise distinct minimal classes of unbounded clique width, and also proves one direction of a conjecture due to Collins, Foniok, Korpelainen, Lozin and Zamaraev. Finally, we show that the other direction of the conjecture is false, since $\\Gamma$ also contains words that are \\emph{not} almost periodic.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-04-01T11:48:14.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "minimal hereditary classes",
      "unbounded clique-width",
      "non-zero letter",
      "pairwise distinct minimal classes",
      "bipartite hereditary graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}