Introduction

A graph is perfect if the vertices of any induced subgraph H can be colored, in such a way that no two adjacent vertices receive the same color, with a number of colors (denoted by $\chi$(H)) not exceeding the cardinality $\omega$(H) of a maximum clique of H. This definition leads to two interesting problems : to determine which graphs are perfect and to produce an optimal coloring of such perfect graphs.

Notions not defined below may be found in [2]. A graph is minimal imperfect if all its proper induced subgraphs are perfect but it is not. It is an easy task to check that an odd chordless cycle (usually called a hole) of length at least five, as well as its complement (usually called an anti-hole), are minimal imperfect graphs. A graph G is said to be Berge if neither G nor $\overline{G}$ contain an odd hole and Claude Berge conjectured that a graph is perfect if, and only if, it is a Berge graph (Strong Perfect Graph Conjecture, SPGC [3]). Berge also conjectured that a graph is perfect if, and only if, its complement graph is pefect [3]. This last conjecture is an easy consequence of the following theorem due to Lovász [11] :

Theorem 1 (The Perfect Graph Theorem - Lovász [11])   A graph G = (V, E) is perfect if, and only if, for every induced subgraph H of G the following inequality holds :

$$\alpha$$(H) ^. $$\omega$$(H) $$\geq$$ | H|.

One can deduce, from this theorem, that in a minimal imperfect graph G = (V, E), with $\alpha$(G) = $\alpha$ and $\omega$(G) = $\omega$, one has (see Lovász [11], Padberg [16]) :

1.

| V| = $\alpha$ ^. $\omega$ + 1;

2.

for every vertex v $\in$ V, G - v has a unique partition into $\alpha$ $\omega$-cliques (i.e. $\alpha$ cliques of size $\omega$) and a unique partition into $\omega$ $\alpha$-stable sets;

3.

each vertex of G belongs to exactly $\alpha$ $\alpha$-stable sets and to exactly $\omega$ $\omega$-cliques.

Bland, Huang and Trotter [4] defined a graph to be partitionable (or ($\alpha$,$\omega$)-partitionable) if there exist two integers $\alpha$,$\omega$ $\geq$ 2 such that (1) and (2) above hold.

For a graph G, we denote by N_G(x) the set of vertices of G adjacent to vertex x of G and by $\mathcal {N}$_G(x) the neighbourhood graph of x induced by N_G(x); when there can be no confusion, we shall write N(x) = N_G(x). As usual, for any graph G = (V, E), we will note n = | V| and m = | E|.

In a minimal imperfect graph, the neighbourhood of any vertex has some interesting properties :

Theorem 2 (Gallai [8])   Let G be a minimal imperfect Berge graph, then for any vertex v of G, $\overline{N_G(v)}$ induces a connected graph.

It is interesting to notice that it is not yet known if $\mathcal {N}$(v) must be connected for any vertex v of a minimal imperfect Berge graph (see Lubiw [12]). In [1] we have proposed a conjecture, weaker than Lubiw's one, dealing with neighbouhood's structural properties in a minimal imperfect Berge graph. In order to formulate this conjecture, we need introduce some definitions.

We call complete join of two (vertex disjoint) graphs A = (V_A, E_A) and B = (V_B, E_B), the graph with the vertex set V_A $\cup$ V_B and the edge set E_A $\cup$ E_B $\cup$ {ab| a $\in$ V_A, b $\in$ V_B}. Let $\mathcal {B}$ be the family of bipartite graphs (possibly reduced to a single vertex) and let $\mathcal {B}$^* be the family, containing $\mathcal {B}$, such that for any two graphs G₁ and G₂ in $\mathcal {B}$^*, the complete join and the disjoint union of G₁ and G₂ are in $\mathcal {B}$^*. It is usefull to notice that if G $\in$ $\mathcal {B}$^*, then every induced subgraph H of G (denoted by H $\subseteq$ G) also satisfies H $\in$ $\mathcal {B}$^*.

Conjecture 1 ([1])   If G is a minimal imperfect Berge graph, then for every vertex v of G we have $\mathcal {N}$_G(v)$\notin$$\mathcal {B}$^*.

Lastly, we need to recall a well known property of minimal imperfect graphs due to Chvátal. A star-cutset of a graph G is a disconnecting set C (i.e. such that G - C has at least two connected components) containing a vertex adjacent to all other vertices of C.

Lemma 1 (Star Cutset Lemma - Chvátal [5])   No minimal imperfect Berge graph contains a star-cutset.

Moreover, one can extend star-cutset lemma for any partitionable graph (see Maire's PhD Thesis [15] for a proof of this fact).