Coloring Mixed Hypergraphs: Theory, Algorithms, and Applications by Vitaly I. Voloshin

Coloring Mixed Hypergraphs: Theory, Algorithms, and Applicationsby Anonymous

Reader Rating:
See Detailed Ratings

March 01, 2005: This book describes a new type of hypergraph coloring in which it is possible to find all the most important concepts of the classical Coloring Theory. In fact, basically, the coloring of mixed hypergraph depends on the coloring of two different types of edges: C-edges and D-edges. In every D-edge there should be at least two vertices colored with Different colors, while in every C-edge there should be at least two vertices colored with a Common color. It is clear that when a mixed hypergraph consists of D-edges only, we obtain the classic colorings introduced for hypergraphs by Erdos and Hainal in 1966. The colorings of mixed hypergraphs are very important in the history of Coloring Theory because in them it is possible to find the well known parameters of the classic theory such as the chromatic number, independence number, chromatic polynomial, etc, but for all these parameters it is possible to find their opposites; for example, the chromatic number, introduced by Erdos, and Hajnal, becomes the minimum number of colors for which there exists a coloring of a mixed hypergraph where all edges are D-edges. During the history of Coloring Theory nobody thought to find the maximum number of colors necessary to color a hypergraph because in classic setting it is trivially equal to the number of vertices of the hypergraph. This problem becomes significant and very difficult when we have a mixed hypergraph where there are only C-edges in opposition to the fact that for it the classic chromatic number (minimum number of colors) is equal to one. In a mixed hypergraph the interaction between C edges and D-edges leads to very many new fundamental concepts, such as uncolorability, unique colorability, perfection with respect to the upper chromatic number, planar mixed hypergraphs, the upper and lower chromatic numbers, broken chromatic spectra, and so on. This book represents an excellent introduction to this new area of research; it is especially useful for students since this direction contains a lot of new open problems of kind that nobody thought before. It is a very easy to read book, self contained, only the very minimum of graph theory knowledge required. The last chapter is of a particular interest; it presents new models of applications of mixed hypergraph coloring. The direction is developing so fast that for 10 years it counts more than 150 scientific publications. I recommend this book to everyone who is interested in contemporary (and future) state of Coloring Theory which is a core of Combinatorics.