Petr Hliněný, Twin-width is linear in the poset width
Zoom ID: 869 4632 6610 (ibsdimag)Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced quite recently, in 2020 by Bonnet, Kim, Thomassé, and Watrigant. One of the core results of these authors is that FO model checking on graph classes of …