{
  "id": "1503.01628",
  "version": "v1",
  "published": "2015-03-05T13:01:54.000Z",
  "updated": "2015-03-05T13:01:54.000Z",
  "title": "Minimal Classes of Graphs of Unbounded Clique-width and Well-quasi-ordering",
  "authors": [
    "A. Atminas",
    "R. Brignall",
    "V. Lozin",
    "J. Stacho"
  ],
  "comment": "20 pages, 9 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Daligault, Rao and Thomass\\'e proposed in 2010 a fascinating conjecture connecting two seemingly unrelated notions: clique-width and well-quasi-ordering. They asked if the clique-width of graphs in a hereditary class which is well-quasi-ordered under labelled induced subgraphs is bounded by a constant. This is equivalent to asking whether every hereditary class of unbounded clique-width has a labelled infinite antichain. We believe the answer to this question is positive and propose a stronger conjecture stating that every minimal hereditary class of graphs of unbounded clique-width has a canonical labelled infinite antichain. To date, only two hereditary classes are known to be minimal with respect to clique-width and each of them is known to contain a canonical antichain. In the present paper, we discover two more minimal hereditary classes of unbounded clique-width and show that both of them contain canonical antichains.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-03-05T13:01:54.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "unbounded clique-width",
      "minimal classes",
      "well-quasi-ordering",
      "minimal hereditary classes",
      "contain canonical antichains"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}