The pentomino exclusion problem, due to \textit{S. W. Golomb} [Polyominoes: puzzles, patterns, problems, and packings (Princeton University Press, Princeton, NJ) (1994; Zbl 0831.05020)], asks for the minimum number of squares in an arrangement \({\mathcal A}\) of unit squares on a \(k\times n\) chessboard \({\mathcal C}_{k,n}\) that has the property that its complement \(\overline{\mathcal A}\) in \({\mathcal C}_{k,n}\) does not contain a pentamino (connected polyomino composed of five unit squares). Such an arrangement \({\mathcal A}\) is said to exclude all pentominoes. Using an appropriate concept of density for infinite plane tilings by polyominoes, the authors derive an asymptotic value for this minimum. They also determine this minimum explicitly for small values of \(k\), \(k\leq 4\).
- New formulas for the pentomino exclusion problem
- scientific article; zbMATH DE number 2064059 (Why is no real title available?)
- scientific article; zbMATH DE number 2064060 (Why is no real title available?)
- Pentomino exclusion and spanning. IP-formulation, valid inequalities and facets
- A generalization of the pentomino exclusion problem: dislocation of graphs
This page was built for publication: On the pentomino exclusion problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5953077)
