{
  "id": "1308.3038",
  "version": "v1",
  "published": "2013-08-14T05:51:50.000Z",
  "updated": "2013-08-14T05:51:50.000Z",
  "title": "Multigraphs with $Δ\\ge 3$ are Totally-$(2Δ-1)$-choosable",
  "authors": [
    "Daniel W. Cranston"
  ],
  "comment": "6 pages, 2 figures",
  "journal": "Graphs and Combinatorics. Vol. 25(1), May 2009, pp. 35-40",
  "categories": [
    "math.CO"
  ],
  "abstract": "The \\emph{total graph} $T(G)$ of a multigraph $G$ has as its vertices the set of edges and vertices of $G$ and has an edge between two vertices if their corresponding elements are either adjacent or incident in $G$. We show that if $G$ has maximum degree $\\Delta(G)$, then $T(G)$ is $(2\\Delta(G)-1)$-choosable. We give a linear-time algorithm that produces such a coloring. The best previous general upper bound for $\\Delta(G) > 3$ was $\\floor{\\frac32\\Delta(G)+2}$, by Borodin et al. When $\\Delta(G)=4$, our algorithm gives a better upper bound. When $\\Delta(G)\\in\\{3,5,6\\}$, our algorithm matches the best known bound. However, because our algorithm is significantly simpler, it runs in linear time (unlike the algorithm of Borodin et al.).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-08-14T05:51:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "multigraph",
      "general upper bound",
      "better upper bound",
      "linear-time algorithm",
      "maximum degree"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1308.3038C"
    }
  }
}