Back close

Total coloring algorithm for graphs

Publication Type : Journal Article

Publisher : Applied Mathematical Sciences

Source : Applied Mathematical Sciences, Hikari Ltd., Volume 9, Number 25-28, p.1297-1302 (2015)

Url :

Keywords : Edge colorings, Independent set, Total coloring algorithm

Campus : Coimbatore

School : School of Engineering

Department : Mathematics

Year : 2015

Abstract : A total coloring of a graph is an assignment of colors to all the elements of graph such that no two adjacent or incident elements receive the same color. Behzad and Vizing conjectured that for any graph G the following inequality holds: Δ(G)+1≤X′′(G)≤Δ(G)+2, where Δ(G) is the maximum degree of G. Total coloring algorithm is a NP-hard algorithm. In this paper, we give the total coloring algorithm for any graph and we discuss the complexity of the algorithm. © 2015 Aman Gupta, J. Geetha and K. Somasundaram.

Cite this Research Publication : Aa Gupta, J. Geetha, and Dr. Somasundaram K., “Total coloring algorithm for graphs”, Applied Mathematical Sciences, vol. 9, pp. 1297-1302, 2015.

Admissions Apply Now