Graph сoloring: an exact algorithm based on preliminary vertex ordering

Abstract

The well-known graph coloring problem is abundant logical inference are used for that, regarded in this paper. A new algorithm is suggested and investigate , based on fixing vertex ordering, which allows to minimize the o f which are given below run-time o f inner cycles. A series or computer experiments on a flow of pseudo-random graphs having up to thousand vertices was conducted to find dependencies of the run-time and the chromatic number on the number of vertices. The area of preferable application of the algorithm is estimated.