GRAPHS AND COMBINATORIAL OPTIMIZATION: THEORY AND APPLICATIONS

This project proposes the study of four different problems in graph theory and combinatorial optimization: intersection graphs; graph coloring problems; variations and subclasses of perfect graphs; and OR applications.

We describe the main hypotheses and questions that will guide our research in each one of them.

Intersection graphs: We propose here the study of two of these classes of graphs: circular-arc graphs and circle graphs. Main open questions about these two classes is to find a characterization by minimal forbidden subgraphs. We will try at least to formulate partial characterizations of both classes.

Graph coloring problems: We are interested in the complexity boundary between vertex coloring and list-coloring. It is an open problem how we can separate (in terms of computational complexity) these extensions of vertex coloring in different classes of graphs. On the other hand, there are interesting non solved problems concerning colorful colorings of graphs.

Variations and subclasses of perfect graphs: We are going to study two known classes of graphs related to perfect graphs. They are clique-perfect graphs and coordinated graphs. With the same idea we mention for circular-arc and circle graphs, we will try to characterize them by minimal forbidden subgraphs. Another interesting open problem is the computational complexity of the recognition of clique-perfect graphs.

OR applications: We consider that we can develop new methodological tools about graph theory and combinatorial optimization, which can be used to solve different applied problems in Operations Research.

Our general goal is to formulate and prove new theoretic properties related to different classes of graphs, and develop models and algorithms using mathematical programming tools to solve applied projects in OR.

The methodology of this project in the theoretical aspects will be the usual in this kind of research: formulate new properties about the classes of graphs mentioned above and try to prove them; analyze the computational complexity of different open problems; adapt known ideas to new problems; etc. On the other hand, we will work in applications of Operations Research. In this case, the methodology will consist on formulating new models and developing new algorithms to solve applied problems. We want to extend the mathematical programming techniques applied to sports scheduling to other problems, in order to feed the practical projects with methodological studies, and vice-versa.