Exploration of recolourable graphs

Port numbers are the usual way an agent tells the edges at a node apart Fraigniaud et al. 2005 Pelc 2019, and most exploration papers also give the agent the port by which it entered. The rotor-router drops the entry port: the agent only follows and advances a pointer stored at the node, which works from any initial pointers Yanovski et al. 2003 Menc et al. 2017. Menc, Pająk and Uznański call this model feature an unknown inport and prove that it costs time even with unbounded node memory Menc et al. 2017. Böckenhauer, Frei, Unger and Wehner removed the port numbers altogether: the agent names a colour and the adversary chooses among the neighbours of that colour, so the colours are the only way to address an edge Böckenhauer et al. 2023. Takahashi, Kanaya, Hiraoka, Eguchi and Sudo note that without port numbers "most commonly used techniques for graph exploration and related problems are no longer applicable" Takahashi et al. 2026. The scale runs from no ports, through ports without the entry port, to ports with it.

In label-guided exploration Cohen et al. 2008 and in the rotor-router Menc et al. 2017 the agent reads only the node it stands on, as in all of single-agent exploration. Böckenhauer, Frei, Unger and Wehner observe that colouring alone "is still utterly useless for an oblivious agent that has to return to the start vertex" when it cannot tell edges apart, and therefore let the agent see the colours of the neighbouring nodes Böckenhauer et al. 2023; every later paper on recolourable exploration keeps this one-hop view Takahashi et al. 2026 Hiraoka et al. 2026. It is the graph analogue of the one-hop visibility of myopic luminous robots, except that what is seen are flags in nodes, not robots.

How little memory an exploring agent needs is the oldest question of the area: no finite automaton explores all graphs Budach 1978 Fraigniaud et al. 2005, and the remedies are markers Blum & Kozen 1978 Disser et al. 2019 or help from a designer Cohen et al. 2008. Recolourable exploration pushes this to the extreme: the agent is oblivious and all memory lives in the nodes Böckenhauer et al. 2023, as in the rotor-router Menc et al. 2017 and the memoryless automaton with pebbles Pattanayak & Pelc 2024. Both later papers ask what a constant number of bits of agent memory would buy Böckenhauer et al. 2023 Takahashi et al. 2026; Inoue, Kitamura, Izumi and Masuzawa compare an oblivious agent with a one-bit agent when nodes hold \(O(\log\Delta)\) bits Inoue et al. 2023.

Fixed colours are the label-guided exploration of Cohen, Fraigniaud, Ilcinkas, Korman and Peleg: a designer writes 2-bit labels at the nodes in advance and a finite automaton reads them Cohen et al. 2008. Böckenhauer, Frei, Unger and Wehner let the agent write the colour itself while exploring, once per node, and showed in a last section that allowing recolouring "radically changes our model": seven colours (eight with the initial one) then explore every graph, against \(n\) without it Böckenhauer et al. 2023. A recolourable node is a whiteboard of \(\log_2 c\) bits; the rotor-router is the special case in which the colour is a pointer that the agent advances on every visit Yanovski et al. 2003 Menc et al. 2017. Whether a colour may return to \(c_0\) matters for exact counts: Böckenhauer et al. intended that it may not, Takahashi et al. allow it, and their six-colour algorithm needs seven colours without it Takahashi et al. 2026.

The rotor-router is studied from arbitrary pointers, which makes it self-stabilizing Yanovski et al. 2003 Bampas et al. 2009 Menc et al. 2017; Bojko, Gotfryd, Kowalski and Pająk call arbitrary initial node memory dirty: with one bit at the agent and one bit per node it can force quadratic time on paths, whereas with clean (uniformly initialised) logarithmic node memory and constant agent memory trees are explored in linear time Bojko et al. 2022. Recolourable exploration starts from a uniform colouring: "at the start of exploration, all nodes are assigned a common initial color" Takahashi et al. 2026. A designer's colouring is the preprocessing of label-guided exploration Cohen et al. 2008. The scale is arbitrary < uniform < designer: an algorithm that works from every colouring works from the uniform one, and a designer may choose the uniform one.

Böckenhauer, Frei, Unger and Wehner note that their general lower bound "relies heavily on the uniformity of the algorithm" and study algorithms that need only explore graphs of a given size \(n\), to see "how useful it is to know the size of the graph in our model" Böckenhauer et al. 2023. As in single-agent exploration, knowing the size is the classical way to let a walk end Aleliunas et al. 1979.

The three requirements are those of single-agent exploration Fraigniaud et al. 2005. Recolourable exploration asks for the hardest, return: "visit every vertex of the graph, return to the start vertex, and terminate" Böckenhauer et al. 2023 Takahashi et al. 2026 Hiraoka et al. 2026. Label-guided exploration asks the agent to stop Cohen et al. 2008, and the rotor-router never stops Yanovski et al. 2003.

Colour counts depend strongly on the class of graphs: for once-colourable nodes trees need four colours and general graphs \(n\) Böckenhauer et al. 2023, and for recolourable nodes the bounds are organised by block structure, three colours for trees and cycles and four for cacti Hiraoka et al. 2026. This axis replaces the model's topology axis because it must order trees below cacti; the other classes studied (triangle-free, φ-free, graphs whose blocks are cycles, complete bipartite graphs or cliques, graphs of bounded circumference) are recorded in the notes.