On essential components and critical sets of a graph (Q1377850)

A minimal imperfect graph (MIG) is one which is imperfect, but every induced subgraph is perfect. The celebrated strong perfect graph conjecture (SPGC) is the assertion that the only MIGs are the odd holes and antiholes. In the study of this conjecture a class of graphs called \((\alpha, \omega)\)-graphs had been introduced and it had been shown that every MIG is an \((\alpha, \omega)\)-graph, but the converse is not true. In this paper the authors study some criticality concepts for edges and their relation to the SPGC. By a subgraph they mean an induced subgraph. (1) An edge is critical if its removal increases the stability number. A chain is critical if it consists of critical edges or a single vertex. A maximal subgraph of a graph \(G\), the vertices of which are connected by critical chains is called a critical component of \(G\). The following two conjectures had been raised earlier by the authors: Conjectures 1. A graph is perfect iff the critical components of all its subgraphs are complete. Conjecture 2. All critical components of a Berge graph are complete. Conjectures 1 and 2 are together equivalent to the SPGC. In fact, it had been proved that Conjecture 1 alone is equivalent to the SPGC. Motivated by these, the authors study, in Section 2, the class MICC of minimal graphs containing an incomplete critical component, and in particular, a Berge graph \(N \) in this class, and show that \(N\) has many of the properties of the \((\alpha,\omega)\)-graphs. Eventually they prove that if, for any \(v\in V(N)\), \(N\setminus v\) has an \(\alpha\)-covering, then \(N\) is an \((\alpha, \omega)\)-graph. (2) A cutset \((V_1,V_2)\) of a graph \(G\) is defined to be augmental if \(\alpha(G(V_1)) +\alpha (G(V_2))> \alpha(G(V))\); otherwise it is non-augmental. An edge \(e=(u,v)\) is essential if each cutset of \(G\) separating \(u\) and \(v\) is augmental. A chain of \(G\) is essential if it consists of essential edges or a single vertex. A maximal subgraph of \(G\), the vertices of which are connected by essential chains is called an essential component of \(G\). It is proved that a graph is perfect iff the essential components of all its subgraphs are complete. This leads to the following conjecture equivalent to the SPGC. Conjecture 3. If the critical components of every subgraph of \(G\) are complete then the essential components of every subgraph of \(G\) are also complete. (3) In the final section the authors study the following generalizations: A set \(E'\) of edges of \(G\) is critical if \(\alpha (G\setminus E') >\alpha(G)\) and \(\alpha (G\setminus E'')= \alpha(G)\) for each \(E'' \subset E'\). An edge is called quasi-critical if it belongs to a critical set of edges.