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.