A Fast Heuristic for Graph B-Coloring Problem
Said Labed, Akram Kout, Salim Chıkhı · 2018
Graph b-coloring can be defined as a proper coloring of vertices in which every color class has a vertex with neighbors in every other class. The b-chromatic number of a graph is the largest number k checking the condition that the graph can be b-colored with k colors. Irving and Manlove, have first defined the notion of b-coloring, proved that finding the b-chromatic number is NP-hard in general and polynomial for trees. In this paper, a new heuristic is proposed to solve the b-coloring problem. Comparisons of experimental results of our proposal to proven results for some graphs, such as trees and regular graphs, proved its efficiency.