This is a question I've spent significant time on! (under a more technical formalization, of course) I've proved that this is not possible in infinite 1-dimensi

This is a question I've spent significant time on! (under a more technical formalization, of course) I've proved that this is not possible in infinite 1-dimensional graphs (like the infinite path, or an infinite grid of size C x Infinity, for a finite number C). For graphs that are infinite in two dimensions I don't have an answer yet (and it's likely that I never will). I'm very fond of this question tho, so if you give me your email (you can contact me at bsuberca@cs.cmu.edu), I can promise to write you back if at some future point in time I have a solution to this, or if someone else shares one with me :)