Ki‐covers. II. Ki‐perfect graphs
Michele Conforti, Derek Gordon Corneil, Ali Ridha Mahjoub · Journal of Graph Theory · 1987
Abstract AKi is a complete subgraph of size i. A Ki‐cover of a graph G(V, E) is a set C of Ki−1s of G such that every Ki in G contains at least one Ki−1 in C. ci(G) is the cardinality of a smallest Ki‐cover of G. A Ki‐packing of G is a set of Kis such that no two Kis have i − 1 nodes in common. pi(G) is the cardinality of a largest Ki‐packing of G. Let Fi(G) denote the set of Kis in G and define ci(F) and pi(F) analogously for F ⊆ Fi(G). G is Ki‐perfect if ∀F ⊆ Fi(G), ci(F) = pi(F). The K2‐perfect graphs are precisely the bipartite graphs. We present a characterization of Ki‐perfect graphs that is similar to the Strong Perfect Graph Conjecture, and explore the relationships between Ki‐perfect graphs and normal hypergraphs. Furthermore, if iA denotes the 0 − 1 matrix of G where the rows are the elements of Fi−1(G) that belong to at least one Ki and the columns are the elements of Fi(G), then we show that iA is perfect iff G is a Ki‐perfect graph. We also characterize the Ki‐perfect graphs for which iAis balanced.