Balanced Graphs

Definition A graph is balanced if every induced cycle has length $0(mod 4)$.

Clearly balanced graphs are bipartite.

A balanced graph is basic if all its vertices on one side of the bipartition have degree at most $2$ or $G$ contains a hole $H$ such that the vertices of $G \setminus H$ 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.