{
  "id": "1206.3862",
  "version": "v4",
  "published": "2012-06-18T09:25:32.000Z",
  "updated": "2018-11-18T03:29:06.000Z",
  "title": "Total coloring of 1-toroidal graphs of maximum degree at least 11 and no adjacent triangles",
  "authors": [
    "Tao Wang"
  ],
  "comment": "10 pages",
  "journal": "Journal of Combinatorial Optimization, 33 (2017) 1090--1105",
  "doi": "10.1007/s10878-016-0025-9",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "A {\\em total coloring} of a graph $G$ is an assignment of colors to the vertices and the edges of $G$ such that every pair of adjacent/incident elements receive distinct colors. The {\\em total chromatic number} of a graph $G$, denoted by $\\chiup''(G)$, is the minimum number of colors in a total coloring of $G$. The well-known Total Coloring Conjecture (TCC) says that every graph with maximum degree $\\Delta$ admits a total coloring with at most $\\Delta + 2$ colors. A graph is {\\em $1$-toroidal} if it can be drawn in torus such that every edge crosses at most one other edge. In this paper, we investigate the total coloring of $1$-toroidal graphs, and prove that the TCC holds for the $1$-toroidal graphs with maximum degree at least~$11$ and some restrictions on the triangles. Consequently, if $G$ is a $1$-toroidal graph with maximum degree $\\Delta$ at least~$11$ and without adjacent triangles, then $G$ admits a total coloring with at most $\\Delta + 2$ colors.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2013-09-16T08:11:23.000Z",
      "abstract": "A {\\em total coloring} of a graph $G$ is an assignment of colors to the vertices and the edges of $G$ such that every pair of adjacent/incident elements receive distinct colors. The {\\em total chromatic number} of a graph $G$, denoted by $\\chiup''(G)$, is the minimum number of colors needed in a total coloring of $G$. The most well-known Total Coloring Conjecture (TCC) says that every graph with maximum degree $\\Delta$ admits a total coloring with at most $\\Delta + 2$ colors. A graph is {\\em 1-toroidal} if it can be drawn on torus such that every edge crosses at most one other edge. In this paper, we investigate the total coloring of 1-toroidal graphs, and prove that the TCC holds for the 1-toroidal graphs with maximum degree at least 11 and some restrictions on the triangles. Consequently, if $G$ is a 1-toroidal graph with maximum degree $\\Delta$ at least 11 and without adjacent triangles, then $G$ admits a total coloring with at most $\\Delta + 2$ colors.",
      "comment": "12 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v4",
      "updated": "2018-11-18T03:29:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "maximum degree",
      "adjacent triangles",
      "adjacent/incident elements receive distinct colors",
      "total chromatic number",
      "well-known total coloring conjecture"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Springer"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.3862W"
    }
  }
}