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.
Profs. Jean Paul Doignon (ULB) and Jean Cardinal (ULB).