Abstract: Origami, where two-dimensional sheets are folded into complex structures, is rich with combinatorial and geometric structure, most of which remains to be fully understood. In this paper we consider flat origami, where the sheet of material is folded into a two-dimensional object, and consider the mountain (convex) and valley (concave) creases that result, called a MV assignment of the crease pattern. An open problem is to count the number of locally valid MV assignments μ of a given flat-foldable crease pattern C, where locally valid means that each vertex will fold flat under μ with no self-intersections of the folded material. In this paper, we solve this problem for a large family of crease patterns by creating a planar graph C* whose 3-colorings are in one-to-one correspondence with the locally valid MV assignments of C. This reduces the problem of enumerating locally valid MV assignments to the enumeration of 3-colorings of graphs.
Based on joint work with William Hoganson, Thomas C. Hull, and Sylvia Wu.