COMBINATORIAL DESIGNS RELATED TO THE STRONG PERFECT GRAPH CONJECTURE

When α, ω are positive integers, we set n = αω + 1 and look for zero-one matrices X, Y of size n × n such that XY= YX = J - I, JX = XJ = αJ, JY = YJ = ωJ. Simple solutions of these matrix equations are easy to find; we describe ways of constructing rather messy ones. Our investigations are motivated by an intimate relationship between the pairs X, Y and minimal imperfect graphs. © 1979.