A note on K i ‐perfect graphs

Ki ‐perfect graphs are a special instance of F ‐ G perfect graphs, where F and G are fixed graphs with F a partial subgraph of G. Given S , a collection of G ‐subgraphs of graph K , an F ‐ G cover of S is a set of T of F ‐subgraphs of K such that each subgraph in S contains as a subgraph a member of T. An F ‐ G packing of S is a subcollection S′ ⊆ S such that no two subgraphs in S′ have an F ‐subgraph in common. K is F ‐ G perfect if for all such S , the minimum cardinality of an F ‐ G cover of S equals the maximum cardinality of an F ‐ G packing of S. Thus K i ‐perfect graphs are precisely K i‐1 ‐ K i perfect graphs. We develop a hypergraph characterization of F ‐ G perfect graphs that leads to an alternate proof of previous results on K i ‐perfect graphs as well as to a characterization of F ‐ G perfect graphs for other instances of F and G .