Total chromatic number of graphs of order 2n+1 having maximum degree 2n-1

Abstract

Let G be a graph of order 2n+1 having maximum degree 2n-1. We prove that the total chromatic number of G is 2n if and only if e(G-w) + alpha'(G-w) greater than or equal to n, where w is a vertex of minimum degree in G, G-w is the complement of G-w, e(G-w) is the size of G-w, and alpha'(G-w) is the edge independence number of G-w.