Gwenaël Joret

Graph coloring problem and facet defining graphs of some polytopes

We consider two topics in graph theory:

• Minimum entropy coloring, a non standard graph coloring problem where we have to minimize a quantity called the entropy of a coloring. We study complexity and approximability issues, and bounds on the number of colors in an optimal coloring.

• Graphs which are linked to facets of the biorder and linear ordering polytopes. Here we are looking for structural results concerning these graphs.

Supervisor:
Profs. Jean Paul Doignon (ULB) and Jean Cardinal (ULB).