Trivially-Perfect Width

摘要

The G-width of a class of graphs Q 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 ∑β of trivially-perfect graphs we show that ISP-width is ∑P-complete and we present fixed-parameter algorithms.