Let G be a plane bipartite graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M such that S is not contained by other perfect matchings of G . The minimum cardinality of forcing sets of M is called the forcing number of M , denoted by f ( G , M ) . Pachter and Kim established a minimax result: for any perfect matching M of G , f ( G , M ) is equal to the maximum number of disjoint M -alternating cycles in G . For a polyomino graph H , we show that for every perfect matching M of H with the maximum or second maximum forcing number, f ( H , M ) is equal to the maximum number of disjoint M -alternating squares in H . This minimax result does not hold in general for other perfect matchings of H with smaller forcing number.
['Xiangqian Zhou', 'Heping Zhang']
A minimax result for perfect matchings of a polyomino graph