  We study a very restrictive graph exploration problem. In our model, an agent
without persistent memory is placed on a vertex of a graph and only sees the
adjacent vertices. The goal is to visit every vertex of the graph, return to
the start vertex, and terminate. The agent does not know through which edge it
entered a vertex. The agent may color the current vertex and can see the colors
of the neighboring vertices in an arbitrary order. The agent may not recolor a
vertex. We investigate the number of colors necessary and sufficient to explore
all graphs. We prove that n-1 colors are necessary and sufficient for
exploration in general, 3 colors are necessary and sufficient if only trees are
to be explored, and min(2k-3,n-1) colors are necessary and min(2k-1,n-1) colors
are sufficient on graphs of size n and circumference $k$, where the
circumference is the length of a longest cycle. This only holds if an algorithm
has to explore all graphs and not merely certain graph classes. We give an
example for a graph class where each graph can be explored with 4 colors,
although the graphs have maximal circumference. Moreover, we prove that
recoloring vertices is very powerful by designing an algorithm with recoloring
that uses only 7 colors and explores all graphs.
