Maximum independent sets in (pyramid, even hole)-free graphs
share
A hole in a graph is an induced cycle with at least 4 vertices. A graph is even-hole-free if it does not contain a hole on an even number of vertices. A pyramid is a graph made of three chordless paths P_1 = a ... b_1, P_2 = a ... b_2, P_3 = a ... b_3 of length at least 1, two of which have length at least 2, vertex-disjoint except at a, and such that b_1b_2b_3 is a triangle and no edges exist between the paths except those of the triangle and the three edges incident with a. We give a polynomial time algorithm to compute a maximum weighted independent set in a even-hole-free graph that contains no pyramid as an induced subgraph. Our result is based on a decomposition theorem and on bounding the number of minimal separators. All our results hold for a slightly larger class of graphs, the class of (square, prism, pyramid, theta, even wheel)-free graphs.
READ FULL TEXT