Trivially-Perfect Width

摘要

The G-width of a class of graphs G is defined as follows. A graph G has G-width k if there are k independent sets N_1, ..., N_k in G such that G can be embedded into a graph H ∈ G with the property that for every edge e in H which is not an edge in G, there exists an i such that both endpoints of e are in N_i. For the class IB of trivially-perfect graphs we show that IB-width is NP-complete and we present fixed-parameter algorithms.