{
  "id": "1105.1906",
  "version": "v1",
  "published": "2011-05-10T11:01:14.000Z",
  "updated": "2011-05-10T11:01:14.000Z",
  "title": "List version of ($p$,1)-total labellings",
  "authors": [
    "Yong Yu",
    "Guanghui Wang",
    "Guizhen Liu"
  ],
  "comment": "11 pages, 2 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "The ($p$,1)-total number $\\lambda_p^T(G)$ of a graph $G$ is the width of the smallest range of integers that suffices to label the vertices and the edges of $G$ such that no two adjacent vertices have the same label, no two incident edges have the same label and the difference between the labels of a vertex and its incident edges is at least $p$. In this paper we consider the list version. Let $L(x)$ be a list of possible colors for all $x\\in V(G)\\cup E(G)$. Define $C_{p,1}^T(G)$ to be the smallest integer $k$ such that for every list assignment with $|L(x)|=k$ for all $x\\in V(G)\\cup E(G)$, $G$ has a ($p$,1)-total labelling $c$ such that $c(x)\\in L(x)$ for all $x\\in V(G)\\cup E(G)$. We call $C_{p,1}^T(G)$ the ($p$,1)-total labelling choosability and $G$ is list $L$-($p$,1)-total labelable. In this paper, we present a conjecture on the upper bound of $C_{p,1}^T$. Furthermore, we study this parameter for paths and trees in Section 2. We also prove that $C_{p,1}^T(K_{1,n})\\leq n+2p-1$ for star $K_{1,n}$ with $p\\geq2, n\\geq3$ in Section 3 and $C_{p,1}^T(G)\\leq \\Delta+2p-1$ for outerplanar graph with $\\Delta\\geq p+3$ in Section 4.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-05-10T11:01:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "list version",
      "incident edges",
      "smallest range",
      "list assignment",
      "outerplanar graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1105.1906Y"
    }
  }
}