Block-graph width

Let G be a class of graphs. A graph G has G-width k if there are k independent sets N1,…,Nk in G such that G can be embedded into a graph H∈G such that for every edge e in H which is not an edge in G, there exists an i such that both endvertices of e are in Ni. For the class B of block graphs we show that graphs with B-width at most 4 are perfect. We also show that B-width is NP-complete and show that it is fixed-parameter tractable. For the class C of complete graphs, similar results are also obtained.