Coloring theory represents one of the central areas of contemporary combinatorics, with a history exceeding 150 years and numerous fundamental applications. Major classical developments include the Four Color Problem of planar graphs, the theory of perfect graphs introduced by Claude Berge in 1960, and hypergraph coloring initiated by Paul Erdős and András Hajnal in 1966.
Classical coloring theory is based on the requirement that in each edge of a hypergraph at least two vertices must have different colors. This leads naturally to the concept of the chromatic number, defined as the minimum number of colors required to satisfy these constraints. Under these conditions, the maximum number of colors is trivially equal to the number of vertices. Thus, classical coloring theory was fundamentally a theory of minimization.
Recognizing the incompleteness of this framework, I introduced in 1992 the concept of an anti-edge of a hypergraph (the idea originated in an unpublished manuscript in 1979). An anti-edge is a subset of vertices in which at least two vertices must have the same color in every proper coloring.
A hypergraph containing both edges and anti-edges was defined as a mixed hypergraph. This framework naturally led to the problem of maximizing the number of colors and to the introduction of the upper chromatic number. Classical coloring theory appears as a special case within this more general framework.
This approach led to numerous new concepts and directions, including strict colorings, chromatic spectra, uniquely colorable mixed hypergraphs, uncolorable mixed hypergraphs, co-perfect mixed hypergraphs, pseudo-chordal mixed hypergraphs, and planar mixed hypergraphs.
A fundamental asymmetry emerged between minimization and maximization problems in coloring theory. This asymmetry affects structural theory, algorithms, computational complexity, and applications. For example, recoloring of vertices becomes unavoidable in general greedy coloring procedures for mixed hypergraphs.
The theory of mixed hypergraph coloring has generated extensive research activity worldwide. The direction was recognized and supported by Paul Erdős in his letter of recommendation. My monograph, Coloring Mixed Hypergraphs: Theory, Algorithms and Applications , was published by the American Mathematical Society in 2002. Reviews of the monograph are available here.
Since its introduction, mixed hypergraph coloring theory has developed into an active international research area with more than 290 scientific publications and continuing growth.
My research program includes theoretical foundations, algorithms, and applications of mixed hypergraphs in computer science, optimization, and related disciplines. I have supervised and collaborated with researchers and students in Moldova, Italy, Germany, Canada, and the United States.
I have participated in more than 35 international conferences, including 15 invited lectures, and have received multiple international research grants and fellowships.
My publication record includes numerous papers and monographs in major international journals. My Erdős number is 2. A list of my publications is available here.
I have taught courses in graph theory, hypergraph theory, discrete mathematics, algorithms, and related areas in the United States, Italy, and Moldova, and supervised multiple Ph.D. theses in mixed hypergraph coloring.
