Rankwidth, graphs on four vertices, and even holes

Rankwidth, graphs on four vertices, and even holes

-
Nicolas Trotignon, ENS de Lyon

Please note that this seminar will take place online via Zoom. You can connect to this seminar via the following link: 

https://princeton.zoom.us/j/810888723

 Jointly with Hoang, we proved that there exist graphs of arbitrarily large rankwidth that can be partitioned into three cliques, such that in each clique, vertices are linearly ordered by the inclusion relation on their neighborhood. During the talk, we will recall what rankwidth is, and describe the construction. The end of the talk will be devoted to explaining how this construction helps to understand several problems, such as coloring when a graph on four vertices is excluded as an induced subgraph, and the structure of even-hole-free-graphs.