Title of article :
Three new upper bounds on the chromatic number
Author/Authors :
Mar?a Soto، نويسنده , , Andre Rossi MD، نويسنده , , Marc Sevaux، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Abstract :
This paper introduces three new upper bounds on the chromatic number, without making any assumptions on the graph structure. The first one, image, is based on the number of edges and nodes, and is to be applied to any connected component of the graph, whereas image and image are based on the degree of the nodes in the graph. The computation complexity of the three-bound computation is assessed. Theoretical and computational comparisons are also made with five well-known bounds from the literature, which demonstrate the superiority of the new upper bounds.
Keywords :
Upper bounding scheme , Graph coloring , Chromatic number
Journal title :
Discrete Applied Mathematics
Journal title :
Discrete Applied Mathematics