Abdallah Saffidine (Univ. South New Wales, Sydney, Australie)

A celebrated result by Roberts [1969] establishes that an interval graph can be represented by unit-length intervals on the real line if and only if no vertex has three non-adjacent neighbors. In 2016, Durán et al. conjectured a generalization of this result, which we recently investigated. We ran an industrial mixed integer programming (MIP) solver on a cluster for several months, looking for a counter-example to the conjecture. With no success in sight, we decided another approach was needed. Going back to the drawing board was surprisingly successful: not only did we prove the conjecture to be true; but we also proved it to be false by exhibiting a counter-example that would have eluded our MIP solver for decades. This talk resolves this apparent inconsistency and can serve as a very gentle introduction to structural graph theory.

Based on joint work with Virginia Ardévol Martínez, Romeo Rizzi, Florian Sikora, and Stéphane Vialette, MFCS 2024.