document: A shy invariant of graphs Moving from a well known result of P.L. Hammer et al. -LRB- 1982 -RRB- , we introduce a new graph invariant , say lambda -LRB- G -RRB- referring to any graph G . It is a non-negative integer which is non-zero whenever G contains particular induced odd cycles or , equivalently , admits a particular minimum clique-partition . We show that -RRB- . -LRB- G -RRB- can be efficiently evaluated and that its determination allows one to reduce the hard problem of computing a minimum clique-cover of a graph to an identical problem of smaller size and special structure . Furthermore , one has alpha -LRB- G -RRB- < or = theta -LRB- G -RRB- - lambda -LRB- G -RRB- , where alpha -LRB- G -RRB- and theta -LRB- G -RRB- respectively denote the cardinality of a maximum stable set of G and of a minimum clique-partition of G
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O B I I O O O O O O O O O
extractive_keyphrases: graph invariant induced odd cycles cardinality maximum stable set
abstractive_keyphrases: minimum clique-partition minimum clique-cover