Graph coloring approach with new upper bounds for the chromatic number: team building application

¹ University of Algiers 3, 02 street Ahmed Ouaked − Dely Brahim, Algiers, Algeria.
² LCOMS Laboratory, Lorraine University Ile-Saulcy 57045 cedex 01, Metz, France.
³ LaROMaD Laboratory, USTHB University BP 32 Bab-Ezzouar 16111, Algiers, Algeria.
⁴ University of Lyon, 42023, University of Jean Monnet, 42000, LASPI, 42334 IUT de Roanne, Roanne, France.

^* Corresponding author: assiausthb@yahoo.fr

Received: 15 May 2017
Accepted: 11 October 2018

Abstract

In this paper, we focus on the coloration approach and estimation of chromatic number. First, we propose an upper bound of the chromatic number based on the orientation algorithm described in previous studies. This upper bound is further improved by developing a novel coloration algorithm. Second, we make a theoretical and empirical comparison of our bounds with Brooks’s bound and Reed’s conjecture for class of triangle-free graphs. Third, we propose an adaptation of our algorithm to deal with the team building problem respecting several hard and soft constraints. Finally, a real case study from healthcare domain is considered for illustration.