From what I gather, you would probably be ok using real, natural-ingredient linoleum, often just called lino, from a print or art supplier. You are not likely to find real linoleum flooring tiles on the shelf at a bigbox store (its more expensive, harder to install, and has a much shorter shelf-life).
Here is another laser-lino-print link:
http://www.cutlasercut.com/blog/printing-with-laser-engraved-lino-blocks-could-rival-traditional-methods-like-screen-printing