An upper bound for the total chromatic number (Q2277479): Difference between revisions

The chromatic number, the edge chromatic number, and the total chromatic number of a graph H are respectively denoted by \(\chi\) (H), \(\chi '(H)\), and \(\chi ''(H)\). Theorem: For any graph H, \(\chi ''(H)\leq \chi '(H)+2\lceil \sqrt{\chi (H)}\rceil.\) Let \(\Delta\) (H) be the maximum degree of graph H. The proof of the theorem relies on the following interesting lemma: Let \(H=(V,E)\) be a graph with \(\chi '(H)=\Delta (H)\) and W be an independent subset of V. Any coloring of W with \(\Delta\) (H) colors can be extended to a proper coloring of \(W\cup E\) with \(\Delta (H)+1\) colors such that if edge e is colored with the new color, then one of the vertices incident with e is in W.