Premium
A note on K i ‐perfect graphs
Author(s) -
Brown Jason I.,
Corneil Derek G.,
Mahjoub A. Ridha
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140306
Subject(s) - combinatorics , mathematics , induced subgraph , strong perfect graph theorem , cardinality (data modeling) , hypergraph , cograph , trivially perfect graph , discrete mathematics , characterization (materials science) , graph , chordal graph , 1 planar graph , computer science , vertex (graph theory) , data mining , materials science , nanotechnology
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 .