{
  "id": "1710.08982",
  "version": "v1",
  "published": "2017-10-24T20:47:29.000Z",
  "updated": "2017-10-24T20:47:29.000Z",
  "title": "$t$-cores for $(Δ+t)$-edge-colouring",
  "authors": [
    "Jessica McDonald",
    "Gregory J. Puleo"
  ],
  "comment": "14 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We extend the edge-coloring notion of core (subgraph induced by the vertices of maximum degree) to $t$-core (subgraph induced by the vertices $v$ with $d(v)+\\mu(v)> \\Delta+t$), and find a sufficient condition for $(\\Delta+t)$-edge-coloring. In particular, we show that for any $t\\geq 0$, if the $t$-core of $G$ has multiplicity at most $t+1$, with its edges of multiplicity $t+1$ inducing a multiforest, then $\\chi'(G) \\leq \\Delta+t$. This extends previous work of Ore, Fournier, and Berge and Fournier. A stronger version of our result (which replaces the multiforest condition with a vertex-ordering condition) generalizes a theorem of Hoffman and Rodger about cores of $\\Delta$-edge-colourable simple graphs. In fact, our bounds hold not only for chromatic index, but for the \\emph{fan number} of a graph, a parameter introduced by Scheide and Stiebitz as an upper bound on chromatic index. We are able to give an exact characterization of the graphs $H$ such that $\\mathrm{Fan}(G) \\leq \\Delta(G)+t$ whenever $G$ has $H$ as its $t$-core.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-10-24T20:47:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "chromatic index",
      "multiforest condition",
      "sufficient condition",
      "edge-colouring",
      "multiplicity"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}