-
Petr Hliněný, Twin-width is linear in the poset width
Petr Hliněný, Twin-width is linear in the poset width
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 …