Scrap quilting is a popular sewing process that involves combining leftover pieces of fabric into traditional patchwork designs. Imagining the possibilities for these leftovers and arranging the fabrics in such a way that achieves visual goals, such as high contrast, can be challenging given the large number of potential fabric assignments within the quilt’s design. We formulate the task of designing a scrap quilt as a graph coloring problem with domain-specific coloring and material constraints. Our interactive tool called ScrapMap helps quilters explore these potential designs given their available materials by leveraging the hierarchy of scrap quilt construction (e.g., quilt blocks and motifs) and providing user-directed automatic block coloring suggestions. Our user evaluation indicates that quilters find ScrapMap useful for helping them consider new ways to use their scraps and create visually striking quilts.