A domino tiling covers a region made of unit squares by nonoverlapping rectangles, each occupying two adjacent squares. Equivalently, it is a perfect matching in the graph whose vertices are squares and whose edges join squares sharing a side. This translates a geometric covering problem into graph theory.
A rectangle has tilings satisfying , with . At the left edge, either one vertical domino leaves a rectangle, or two horizontal dominoes leave a rectangle. Hence , and . A checkerboard colouring gives a different tool: every domino covers one square of each colour, so unequal colour counts obstruct a tiling. Equal counts are necessary but need not suffice for arbitrary regions.
Articles by others on the same topic
Domino tiling is a mathematical concept that involves covering a given area (usually a rectangular region) with dominoes, where a domino is a rectangular piece that covers two adjacent unit squares. In the context of combinatorial mathematics and theoretical computer science, domino tilings are often explored in relation to various problems such as counting configurations, studying combinatorial effects, and examining properties of different types of grids.