Shoma Hiraoka

Color Complexity of Recolorable Graph Exploration: Upper and Lower Bounds via Block Structure

We study exploration of anonymous, port-free graphs by a single agent with no internal memory. To compensate for the lack of memory, the agent uses writable vertex colors as external memory. From every starting vertex, the agent must visit all vertices, return to its start, and terminate there. Throughout, recoloring i...