Preface

The Theory of Graph Coloring has existed for more than 150 years. From its modest beginning of determining whether a geographic map can be colored with four colors, the theory has become central in Discrete Mathematics with many contemporary generalizations and applications. Historically, graph coloring involved finding the minimum number of colors to be assigned to the vertices so that adjacent vertices must have different colors.

In this book we introduce the theory of coloring mixed hypergraphs where problems on both the minimum and maximum number of colors occur. Mixed hypergraphs contain two families of (hyper)edges: classic edges and their opposites which may be viewed as “anti-edges". In every coloring, classic edges have at least two vertices of distinct colors, while the “anti-edges" have at least two vertices of the same color. The interaction between edges and “anti-edges" constitutes the main feature of coloring of mixed hypergraphs. This interaction brings many new properties to the theory of colorings, for example: colorability, unique colorability, lower and upper chromatic numbers, perfection with respect to the upper chromatic number, and broken chromatic spectra.

Perhaps the main conclusion is that in trying to establish a formal symmetry between the two types of constraints expressed by the edges and “anti-edges" we find a deep asymmetry between the problems on minimum and problems on maximum number of colors. This asymmetry pervades the theory, methods, algorithms and applications of mixed hypergraph coloring.

This book will appeal to a broad audience. It draws together the theory, algorithms and applications of mixed hypergraph coloring and thus is appealing to researchers in Discrete Mathematics, Operations Research, and Computer Science. Furthermore the book presents some new and challenging problems that should attract graduate students looking for thesis topics.