Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Graph colouring and variations
Авторы: Werra D., Hertz A.
Graph coloring has been a field of attraction for many years; a wide collection of papers has been dedicated to the study of chromatic properties of graphs. Initially such problems were just a kind of game for pure mathematicians; it was in particular the case of the famous four color problem. However, as people were getting used to applying the tools of graph theory for solving real-life organizational problems, chromatic models appeared as a quite natural way of tackling many situations. Among these are timetabling problems, or more generally scheduling with disjunctive constraints (pairwise incompatibility between jobs), clustering in statistics, automatic classification, group technology in production (partitioning a collection of parts into families of parts which are as similar as possible in their production process), VLSI design, etc.
The theory of perfect graphs and particularly the perfect graph conjecture of Claude Berge provided a strong impetus for the development of the theory of coloring. Several papers in this volume are dealing with special classes of perfect graphs which are characterized by chromatic properties. A natural extension of coloring problems - motivated by a polyhedral formulation of optimization in perfect graphs - consists in expressing an integral vector in a polyhedron as a sum of integral vectors contained in a smaller polyhedron. This extension is considered in some contributions of the present volume. Besides this, color-critical graphs have been a focusing point in many research works; such graphs, having some inherent structure, can hopefully be characterized by more and more properties.