| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418532 | Discrete Applied Mathematics | 2011 | 9 Pages |
This paper introduces three new upper bounds on the chromatic number, without making any assumptions on the graph structure. The first one, ξξ, is based on the number of edges and nodes, and is to be applied to any connected component of the graph, whereas ζζ and ηη 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.
► Three new upper bounds on the chromatic number. ► The first one is based on the number of edges and nodes. ► The remaining ones are based on the degree of the nodes in the graph. ► These bounds are theoretical and computational better than literature bounds.
