Séminaire

We will present the proof of the above theorem, which partially answers a question raised by De Fraysseix and Ossona de Mendez. Their open problem is, Is every $k$-colorable planar graph the intersection graph of segments using $k$ slopes ?. It was known to hold for $k=2$. Here we prove the case $k=3$. The case $k=4$ is open and is also known as West’s conjecture. As in these intersection models, parallel segments are expected to be pairwise disjoint, this conjecture generalizes both the 4-color theorem and the fact that every planar graph is an intersection graph of segments. A crucial point in our proof is the use of a system of linear equations, which provides a scheme of the solution. It is shown that this system always has a (unique) solution by studying the perfect matchings of some related planar graph. At the end of the talk we will briefly discuss how West’s conjecture could be tackled using a similar approach.