$t$-cores for $(\Delta +t)$-edge-colouring

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\ge 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 }^{\prime }(G)\le \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)\le \Delta (G)+t$ whenever $G$ has $H$ as its $t$-core.

15 pages, 2 figures. This version fixes an issue with the definition of the fan number, and makes several smaller improvements