Two bounds of chromatic number in graphs coloring problem
Assia Gueham, Anass Nagih, Hacène Aït Haddadène · 2014
In this paper, we focus on the coloration approach and estimation of chromatic number. We propose an upper bound of a chromatic number based on the orientation algorithm described in [4]. This upper bound is improved by developing a novel coloration algorithm. Finally, we make a theoretical and empirical comparison of our bounds with Brooks's bound and Reed's conjecture [15] for class of triangle-free graphs.