Classical Coloring of Graphs

Despite the variety of graph coloring models discussed in published papers of a theoretical nature, the classical model remains one of the most significant and widely applied in practice. The NP-hardness of the coloring problem gives rise to the necessity of using suboptimal methods in a wide range of practical applica- tions. Moreover, the large range of problems solved by classical coloring, as well as the variety of graph families

with practical significance in this field aids the evolu- tion and development of new suboptimal algorithms. There exist several relatively simple methods, which are regarded as classical due to their date of creation or scope of practical application. As the implementation of a particular algorithmic solution requires the selection of at least one coloring method, it is essential to for- mulate criteria for the assessment of the suitability of coloring algorithms. Speed of operation, measured through computational complexity, is obviously one of the most important features which are taken into consideration when selecting a graph coloring approach. For suboptimal methods, the algorithm’s performance guar- antee is another characteristic feature, describing how accurate, or more precisely how inaccurate the obtained results may be. The analysis of the smallest hard to color graphs is yet another criterium, which in a certain sense complements the performance guarantee. 1.1. Basic terms and definitions Definition 1.1. A graph G is an ordered pair G = (V,E), where V stands for a finite set of elements called vertices, while E – a finite set of unordered pairs of vertices called edges. The cardinality of the set of vertices V is denoted by the symbol n =...

Website: fileadmin.cs.lth.se | Filesize: -
No of Page(s): 19
Download Classical Coloring of Graphs.pdf