  We give a combinatorial polynomial-time algorithm to find a maximum weight
independent set in perfect graphs of bounded degree that do not contain a prism
or a hole of length four as an induced subgraph. An even pair in a graph is a
pair of vertices all induced paths between which are even. An even set is a set
of vertices every two of which are an even pair. We show that every perfect
graph that does not contain a prism or a hole of length four as an induced
subgraph has a balanced separator which is the union of a bounded number of
even sets, where the bound depends only on the maximum degree of the graph.
This allows us to solve the maximum weight independent set problem using the
well-known submodular function minimization algorithm.

Combinatorics