Coloring Graphs to Avoid Monochromatic Cycles

Frits Spieksma, K.U. Leuven

Given a directed graph, is it possible to color each vertex red or blue such that no monochromatic cycle occurs? This question was motivated by an economic application (concerning the rationality of household behavior) that we will discuss in some detail. We will also describe heuristics as well as an enumerative approach in order to find an answer to the question above.

This is joint, ongoing work with Fabrice Talla Nobibon, Laurens Cherchye, Bram De Rock, and Jeroen Sabbe.

back to EIDMA Seminar Combinatorial Theory announcements