■ドミノ被覆・畳被覆(その1)

 これまで,本コラムでは種々の被覆問題を取り上げてきた.

[1]切り取りチェス盤がドミノで被覆できないのはなぜか?

 一方が30頂点,他方が32頂点の2部グラフだから

[2]m×nチェス盤のドミノ被覆で分断線ができないのは?

 mnが偶数で,m≧5,n≧5かつ(m,n)≠(6,6)のときに限り存在する

 もっと風変わりな被覆としては

[3]モノミノ,ドミノ,トロミノで被覆する

[4]3色のドミノで,同じ色が隣り同士にならないように被覆する

等々.

===================================

 ところで,日本の畳は1×2の長方形で,4枚の畳が角で合わないように敷き詰める.

 すべての畳敷き集合はヒッカーソンによって特徴づけられていて,対応する母関数はラスキーとウッドコックによって得られている.

  Electronic J Combinatorics 16.1 (2009) #R126

===================================