Volume 52, Number 3, July–September 2018
|Page(s)||807 - 818|
|Published online||26 September 2018|
Graph coloring approach with new upper bounds for the chromatic number: team building application
University of Algiers 3,
02 street Ahmed Ouaked − Dely Brahim,
2 LCOMS Laboratory, Lorraine University Ile-Saulcy 57045 cedex 01, Metz, France.
3 LaROMaD Laboratory, USTHB University BP 32 Bab-Ezzouar 16111, Algiers, Algeria.
4 University of Lyon, 42023, University of Jean Monnet, 42000, LASPI, 42334 IUT de Roanne, Roanne, France.
* Corresponding author: firstname.lastname@example.org
Accepted: 11 October 2018
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.
Mathematics Subject Classification: 05C85 / 68R10
Key words: Chromatic number / graph orientation / graph coloring / team building / healthcare
© EDP Sciences, ROADEF, SMAI 2018
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.