On the boolean-width of a graph: structure and applications

Y. Rabinovich, J. A. Telle

We study the recently introduced boolean-width of graphs. Our structural results are as follows. Firstly, we show that almost surely the boolean-width of a random graph on $n$ vert…