Generalization of graph coloring-type problems to mixed hypergraphs brings many new dimensions to the theory of colorings. A main feature of this book is that in the case of hypergraphs, there exist problems on both the minimum and the maximum number of colors. This feature pervades the theory, methods, algorithms, and applications of mixed hypergraph coloring.
The book has broad appeal. It will be of interest to both pure and applied mathematicians, particularly those in the areas of discrete mathematics, combinatorial optimization, operations research, computer science, software engineering, molecular biology, and related businesses and industries. It also makes a nice supplementary text for courses in graph theory and discrete mathematics. This is especially useful for students in combinatorics and optimization. Since the area is new, students will have the chance at this stage to obtain results that may become classic in the future.
Mixed hypergraphs were introduced by the author in 1992, and since then the field has grown significantly and many interesting connections to other colouring problems have been discovered; the last chapter of the book is devoted to these connections. In some aspects, colouring mixed hypergraphs is analogous to the usual colouring, while in others it is completely different - for example, there exists a mixed hypergraph on six vertices that can be coloured with two and four colours but has no proper colouring with exactly three colours. The field is developing so rapidly that the author could not include some recent results, and several problems listed as open have since been solved.
The book is self-contained and very readable. It is clearly organised: each of the twelve chapters is devoted to a single concept or a single class of mixed hypergaphs. Anybody interested in graph or hypergraph colouring will find this book interesting.
The main feature is that mixed hypergraphs represent structures in which problems on both the minimum and maximum number of colours occur. The author develops the theory with all the results obtained to date. This book will be a useful reference text for people who study hypergraphs as well as related fields and applications. The level of the text is aimed at graduate and research use.
In the introduction, the author gives an overview of graph colouring, introduces the idea of mixed hypergraph colouring, and describes unforeseen features and philosophical motivation. In the first chapter he surveys results related to the lower chromatic number. Subsequent chapters are devoted to uncolourable (having no colourings), uniquely colourable (having a unique feasible partition), $C$-perfect (having perfection with respect to the upper chromatic number), interval (generalizations of interval hypergraphs), pseudo-chordal (generalizations of chordal graphs) and circular (generalizations of cycle) mixed hypergraphs. Of special interest and fundamental importance are the chapters describing the gaps in the chromatic spectrum (they are not possible in classic colourings), planar mixed hypergraphs (generalizations of planar graphs) and colourings of block designs (Steiner triple and quadruple systems), considered as mixed hypergraphs. The last chapter contains 10 models of application of the concept of mixed hypergraph (ranging from computer science to molecular biology). Each chapter ends with a list of open problems, and the book contains many algorithms.
It is worth mentioning that the author maintains the mixed hypergraph colouring web site at \url{http://math.net.md/voloshin/mh.html}, which in addition to detailed material about the monograph contains a list of all publications on this new scientific direction.
Reviewed by Mario Gionfriddo
The material is organized as follows from the table of contents: Introduction. (I) The lower chromatic number of a hypergraph. (II) Mixed hypergraphs and the upper chromatic number. (III) Uncolorable mixed hypergraphs. (IV) Uniquely colorable mixed hypergraphs. (V) ${\cal C}$-perfect mixed hypergraphs. (VI) Gaps in the chromatic spectrum. (VII) Interval mixed hypergraphs. (VIII) Pseudo-chordal mixed hypergraphs. (IX) Circular mixed hypergraphs. (X) Planar mixed hypergraphs. (XI) Coloring block designs on mixed hypergraphs. (XII) Modelling with mixed hypergraphs.
The book should be of interest to those studying colorings of hypergraphs and is recommended.
Dan S. Archdeacon (Burlington)
On the theoretical and epistemological level, often there is not a dialogue, but a split between these languages. It is contrasting with an acquisition of consciousness as indispensable premise of the sense of responsibility and collaboration by which all the scientific disciplines - physical, mathematical, natural and social - are called to realize their own operating capacities.
If this is true, if a communication and connection - or rather, 'inter-connection' of subjects and concepts, and not only their mechanic 'inter-action' - between different fields of knowledge, and between science and philosophy, is fundamental, the explicit reference of the Author of this book of mathematics to some considerable philosophical concepts results particularly significant, and atypical.
The A. intends to carry out 'mathematically' a rediscovery of the Hegelian thought. He refers to philosophical categories for a resumption of the dialectical conception, in which also "the evolution of ideas occurs through a dialectical process", never definitively concluded. The A. affirms that such philosophical conception is at the basis of its innovative mathematical theory on the "Mixed Hypergraph Coloring", and in this theory it finds, at the same time, an emblematic scientific confirmation.
This theory, which is gaining an important place in Discrete Mathematics, moves from the concept of "hypergraph": it is a set of points called "vertices" and a collection of subsets of arbitrary size, called "edges". The vertices are drawn by points, and the edges by curves encircling respective subsets. The concept of "mixed hypergraph" is thought by the A. in terms of dialectical synthesis between two conflicting ideas: those of "D-edges" (the letter D stands for "Different"), which corresponds to a thesis, and those of "C-edges", or "anti-edges" (the letter C stands for "Common"), which corresponds to an antithesis. Due to interplay between C-edges and D-edges, many new mathematical properties (="qualities") have been discovered, which are not possible in classical coloring theory. The understanding of consequences of this theory in Discrete Mathematics is still on the way.
From the philosophical view point, there is an evident presence of the dialectical concept of 'contradiction'. It allows to observe that this mathematical theory represents a rare case in which the formal logic not only accepts, but studies the contradictions. So doing, the A. refutes those who retain that dialectics is not treatable by the formal logic, that is to say, the dialectical logic is not 'formalizable'.
Not only. The A. shows that dialectics is, in accordance with the Hegelian philosophy, form and substance, method and content at the same time. In fact, in his theory the dialectics constitutes a 'method' of study, as well as an 'object' of study. In other words, the dialectics here is recognizable also on the methodological - in addition to that one of the contents - level. In this way, the A. can answer effectively also to those who, diverging from Hegel, consider dialectics, for the most part, only as a method.
The question of the contradictions, or antinomies, has been tackled, in the past, by many great mathematicians: from Frege to Russell, to Brouwer. In particular, it is necessary to mention the formalistic program of Hilbert, outstretched to guarantee the certainty of the mathematics through the demonstration of the uncontradictoriness of his theories, based on axiomatical and auto-evident principles. But then, Godel showed that such absence of contradictions in a formal system is untenable.
The mathematical thought, therefore, arrived to accept the contradictions, that is to admit their unavoidably. But only a special logic, namely the 'dialectical' logic, admits and theorizes itself the contradictions, which are resolved and surpassed without to be denied (see the Hegelian "Aufhebung"). So, the theory expressed by the A. constitutes a new mathematical orientation, based on a 'dialectical' logic which does not refuse the 'formal' logic. It results heterogeneous if compared to the above-mentioned orientations, but in syntony with the Godelian turning point.
The A. seems besides to advise, in his theory, that all contradictions are assimilable to the fundamental contradiction between 'to be the same' and 'to be different'. Already this indication about some, not only mathematical, aspects of the theory shows that it is in connection with different planes of research, including philosophical-social level. Not at random, there is a clear reference to conceptual categories which are recurring in the contemporary philosophy, as those of 'identity' and 'difference'. For example, the last section shows that the notion of the natural number is the most selfcontradictory notion that can ever exist if we consider the contradictions between "identity" and "difference" categories expressed in mathematical language of colorings. In such perspective, it appears interesting to observe how these categories, elaborated mostly by the philosophical thought, are conceivable by the scientific thought.
So, such categories can receive various contributions of theoretical elaboration, in order to their adequate, and not superficial, delineation. It becomes possible, in this way, to avoid the risk of misleading simplifications - always having negative practices results - which come to create a great deal of platitudes uncritically admitted in the mechanisms of functioning of the social system.
It may hence be inferred the importance of a study, like that one accomplished in this book, which contributes, more or less explicitly, to a rigorous elaboration of categories-key as those above-mentioned of 'contradiction', 'identity', 'difference', and also of 'negation' and 'dialectics'.
Their framing through the formal logic of the mathematical language can put in light some heuristic and methodological tools which are available to mathematicians, and scientists in general, including scholars of social sciences. The formalism itself, very important also in the legal logic and in the concrete experience of the law, cannot be fully understood without the reference to the mathematical logic and to the epistemological procedures emerging from it.
In the case in point, the reference to the dialectical logic, mathematically argued, can be seen as a further and indirect assertion, in accordance with the limits of the formalism showed by Godel, of the unexhaustive nature of the formal logic, but without to deny its indispensability.
Barbara Troncarelli