A total-chromatic number analogue of Plantholt's theorem (Q750449)

Let \(n\geq 1\), let J be a subgraph of \(K_{2n}\), let \(e=| E(J)|\) and let j be the maximum size of a matching in J. In this paper it is proved that \(\chi_ T(K_{2n}\setminus E(J))=2n+1\) \((=\chi_ T(K_{2n}))\) if and only if \(e+j\leq n-1,\) thus obtaining a total- chromatic number analogue of Plantholt's theorem about the chromatic index of the graph obtained from \(K_{2n+1}\) by removing just a few edges. Under the same hypotheses it is also shown that \(\chi_ T(H)=\Delta (H)+2\) if \(e+j\leq n-1\) and \(\chi_ T(H)=\Delta (H)+1\) if \(n\leq e+j\leq 2n-1,\) where \(H=K_{2n}\setminus E(J).\) A conjecture about related problems is proposed.