**Definition** A graph is *balanced* if every induced cycle has length
.

Clearly balanced graphs are bipartite.

A balanced graph is *basic* if all its vertices on one side of the
bipartition have degree at most
or contains a hole such that
the vertices of induce a complete bipartite graph.

Here are two conjectures concerning balanced graphs.

**Conjecture 1** (Conforti, Cornuejóls,Rao) Every balanced graph is either
basic or has a 2-join or a skew-partition.

**Conjecture 2** (Conforti, Rao) In every balanced graph, there exists an
edge that can be deleted, so that the resulting graph remains balanced.

Contributed by Gerard Cornuejòls

Back to the
main index
for Perfect Graphs.