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

Shoma Hiraoka, Shunsuke Imori, Shota Takahashi +1

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 extern…