Coloring Theory represents a core of contemporary Combinatorics.
It has a history of more than 150 years and many important applications.
The most important and developed topics are related to
the famous four color problem of planar graphs (inherited from the
19th century), perfect graphs
(introduced by C.Berge in 1960) and coloring of hypergraphs (initiated
by P.Erdös and A.Hajnal in 1966).

All Coloring Theory in the most general setting was based on the fundamental notion of coloring the vertices of a hypergraph such that at least two vertices in each edge have DIFFERENT colors. Hence, the notion of chromatic number follows: it is the minimum number of colors to color the vertices of a hypergraph to meet these requirements. Since in these constraints the maximum number of colors is trivially equal to the number of vertices, one might state that all the theory was the theory on the minimum. From this point of view, its incompleteness is evident.

I have come to conclusion that the language of edges is not relevant for problems on the maximum number of colors, and therefore it is necessary to consider a new type of subsets.
In 1992, I introduced the notion of an anti-edge of a hypergraph (the idea dates back to
1979, unpublished manuscript).
The anti-edge is a subset of vertices which in every coloring has at least two
vertices of the SAME color.
A hypergraph with both edges and anti-edges was called mixed hypergraph.
For a mixed hypergraph
the problem to find the maximum number of colors arises. Hence the notion of
the upper chromatic number of a hypergraph appeared.
Under the frame of this, classic theory of coloring became a special case.

The idea of mixed hypergraph has led to the notions of strict colorings, chromatic spectrum, uncolorable (having no colorings), uniquely colorable (generalizations of cliques), co-perfect (with respect to the upper chromatic number), pseudo-chordal (generalizations of chordal graphs), planar (generalizations of planar graphs) mixed hypergraphs and many other.

It turned out that there exists a difference of principle between problems on the minimum and problems on the maximum number of colors in what concerns theory, algorithms, complexity and applications. For example, the re-coloring of colored vertices is unavoidable in general greedy algorithm.
It has generated a number of new directions of research in
Coloring Theory and in Combinatorics in general. All they may be
found in my papers and in papers of many mathematicians.
The
direction was appreciated by Paul Erdös in his
letter of
recommendation. The monograph
"Coloring Mixed Hypergraphs: theory, algorithms and applications"
was published by the AMS in 2002. The reviews of the monograph can
be found here.

I have an active program for further research in the theory of mixed hypergraphs and their applications (range from computer science to molecular biology) that is greatly stimulated by my contacts with mathematicians and computer scientists in many countries. A number of students in Moldova, Italy, Germany, Canada, USA and other countries have started research under my supervision and consulting on coloring of mixed hypergraphs and obtained important results.

Since 1993 I participated at more than 25 international conferences (10 as an invited speaker), obtained 8 grants of CNR (Italy), 4 German grants (Volkswagen Stiftung, DAAD, DFG, DFG), 2 grants of National Research Council (USA, Georgia State University and University of Illinois), won a Cariplo Fellowship (Politecnico di Milano), and was invited as Visiting Professor in the University of Toronto, University of Catania, University of Illinois at Urbana-Champaign, University of Delaware, as Visiting Scientist at McMaster University (Hamilton), Wilfrid Laurier University (Waterloo), and Visiting Member at Fields Institute (Toronto). In 1998 and 2002 I served as a Ph.D. thesis committee member, University of Illinois (Urbana-Champaign). Being at Troy State University, I obtained 3 research grants.

I have many scientific publications including monograph and many papers published in major international journals, my Erdös number is 2, my NONSELF-CITATION INDEX can be found here.

The scientific direction of mixed hypergraph coloring that I founded, since 1993 counts more than 200 publications and is continuously expanding (about one paper a month around the world).

During 1984-1994 I have written more than 250 Abstracts for the Soviet (Russian) Abstracting Journal "Mathematics", section "Graph Theory". With my secondary interests in Computer Science, I have developed the Hypergraph Drawing and Optimization System, a software realized by my students at Moldova State University (taken to the 25 universities of the world).

In USA I taught Introduction to Graph Theory, Discrete Mathematics, Calculus, Algebraic Structures, Introduction to Advanced Mathematics and Proof Technique, Probability and Statistics and Foundations of Mathematics. In Italy I taught advanced course on Coloring of Hypergraphs. In Moldova I taught advanced courses in graph and hypergraph theory and algorithms, lectures and practical training on Informatics, Data Bases, Computer Aided Design, supervising 3-5 annual theses and 2-5 master theses yearly.

There are 6 Ph.D. theses on coloring mixed hypergraphs defended: three in Italy, 1996 (special award of CNR) and 2002, 2003, and three under my supervision in Moldova (E. Flocos 1998, A. Niculitsa 2000, V. Prisacaru 2000).

Since 1995, I am a referee for a number of major international journals in the field.

Back to Home Page