A Class of Perfect Graphs
James B. Shearer · SIAM Journal on Algebraic and Discrete Methods · 1982
Let P be a simply connected polyomino. Let $G( P )$ be the graph whose vertices are the maximal rectangles in P, two such vertices being adjacent if the corresponding rectangles have nontrivial intersection. In this paper we show that $G ( P )$ is perfect. This solves a problem posed by Berge et al.