{
  "id": "1112.3254",
  "version": "v1",
  "published": "2011-12-14T15:47:43.000Z",
  "updated": "2011-12-14T15:47:43.000Z",
  "title": "Recognizing [h,2,1] graphs",
  "authors": [
    "Liliana Alcón",
    "Marisa Gutierrez",
    "María Pía Mazzoleni"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex of G such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at mots s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted [h,s,t]. An undirected graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree. In this paper we characterize [h,2,1] graphs using chromatic number. We show that the problem of deciding whether a given VPT graph belongs to [h,2,1] is NP-complete, while the problem of deciding whether the graph belongs to [h,2,1]-[h-1,2,1] is NP-hard. Both problems remain hard even when restricted to $Split \\cap VPT$. Additionally, we present a non-trivial subclass of $Split \\cap VPT$ in which these problems are polynomial time solvable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-12-14T15:47:43.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C62"
    ],
    "keywords": [
      "maximum degree",
      "problems remain hard",
      "vpt graph belongs",
      "vertex intersection graph",
      "polynomial time"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1112.3254A"
    }
  }
}