Exploration of recolourable graphs
A single agent with little or no memory must visit every node of an anonymous graph whose nodes carry colours it can read and rewrite; how many colours are needed, and how much does it help to recolour, to see neighbours or to have port numbers?
Problem statement and measuresexpand
A single deterministic agent starts at a node \(s\) of a connected, simple, undirected, anonymous graph \(G=(V,E)\) with \(n\) nodes, \(m\) edges, maximum degree \(\Delta\) and diameter \(D\). Every node \(v\) holds a colour \(\psi(v)\) from a palette of \(c\) colours that persists between visits. In each step the agent at \(v\) observes \(\psi(v)\) (and, depending on the setting, \(\deg(v)\), port numbers, the entry port, and the multiset of its neighbours' colours), sets \(\psi(v)\) to a new colour (recolours \(v\)) if the setting allows it, and then moves to a neighbour or stops. In the main model Böckenhauer et al. 2023 there are no port numbers: the agent names a colour and the adversary moves it to any neighbour of that colour; the agent is oblivious (it keeps no memory between steps); all nodes start with the initial colour \(c_0\); and the agent must visit every node, return to \(s\) and stop there, from every start and against every adversary. Other settings fix the colours in advance (label-guided exploration), give port numbers, or ask only for perpetual exploration. Measures: the number of colours \(c\), counting \(c_0\) (the main measure); time, the number of moves (traversals of one edge) until termination (or until every node is visited, for perpetual exploration); and the agent's memory. All known results are for one agent.
Measures: Colours, number \(c\) of node colours, counting the initial colour \(c_0\) (for the rotor-router: per node); Time, moves until the agent stops (perpetual: until every node is visited); Memory, bits of agent memory; 0 for an oblivious agent.
Recolourable nodes, oblivious agent, any graph
standard settingverifiedAn oblivious agent without port numbers explores every graph and returns with six colours; at least four are needed.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Port numbers: no ports
- Edges carry no port numbers. To move, the agent at \(v\) names a colour \(x\); the adversary moves it to any neighbour \(u\) of \(v\) with \(\psi(u) = x\) (if the agent sees no neighbour colours, to any neighbour). The agent never learns by which edge it arrived.
- View: neighbour colours
- At node \(v\) the agent observes \(\psi(v)\) and the multiset \(\{\!\{\psi(u) : u \in N(v)\}\!\}\) of its neighbours' colours (hence also \(\deg(v)\)), without knowing which edge leads to which colour unless ports say so.
- Agent memory: oblivious
- The agent has no internal state: its action (new colour of \(v\), then a move, stay or stop) is a function of its current observation only. Called zero-memory, memoryless or a 1-state robot.
- Recolouring: recolourable
- At every step the agent at \(v\) may set \(\psi(v)\) to any colour of the palette, including back to \(c_0\), any number of times (the convention of Takahashi et al. 2026 and Hiraoka et al. 2026).
- Initial colouring: uniform \(c_0\)
- Initially \(\psi(v) = c_0\) for every node \(v\) (clean node memory). The colour \(c_0\) counts as one of the \(c\) colours.
- Knowledge: nothing known
- The algorithm is the same for all graphs: it knows neither \(n\) nor \(\Delta\) nor any other parameter (a uniform algorithm in Böckenhauer et al. 2023).
- Termination requirement: return
- The agent visits every node and then halts at its start node \(s\) (exploration with return).
- Network: any graph
- A finite, simple, connected, undirected, anonymous graph \(G = (V,E)\) with \(n\) nodes.
Statement for this variant
The BFUW model: no port numbers, the agent sees the colour of its node and the multiset of its neighbours' colours, recolours its node freely and names a colour to move to; the adversary chooses among neighbours of that colour. All nodes start with \(c_0\). The agent must visit every node, return to \(s\) and stop there, for every start and every adversary. Colours are counted including \(c_0\).
What is known
- no single rule with at most three colours explores every subcubic pseudotree (graphs with maximum degree three and at most one cycle; Theorem 13)
- realised on a family of nine graphs with at most five nodes, among them \(C_3\), \(C_4\), \(C_5\) and \(K_{1,3}\)
- computer-assisted: the cases left after a hand reduction are refuted by a SAT solver with a DRAT-checked certificate
- uses that two executions from different starts which reach the same configuration cannot both stop at their own start (Lemma 2)
- trivial: any agent must visit all \(n\) nodes (stated for trees in Bojko et al. 2022)
Results, in order of publication
Theorem 11 (stated as 7 colours: the paper does not count \(c_0\)). Breadth-first: a node at depth \(j\) gets label \((j \bmod 3)+1\), in green or red according to the phase, plus a colour for deleted (finished) nodes. Never recolours a node back to \(c_0\). Time not analysed.
Theorem 1: semi-DFS, a depth-first search whose return path is kept an induced path, so that the predecessor of the head is its only neighbour on the path; colours init, path, fin, head1, head2, neigh. Time not analysed.
Open questions
Is the colour complexity of recolourable exploration of arbitrary graphs 4, 5 or 6 Takahashi et al. 2026 Hiraoka et al. 2026?
Give a proof of the four-colour lower bound without computer assistance, or for a single graph Hiraoka et al. 2026.
How many moves does a constant-colour algorithm need on general graphs? No bound is known; for graphs whose blocks are cliques or triangle-free, five colours and \(O(n\Delta)\) moves suffice Hiraoka et al. 2026.
How many colours suffice if the agent has a constant number of bits, or even one bit, of memory, or may move at random Böckenhauer et al. 2023 Takahashi et al. 2026?
Does forbidding recolouring back to \(c_0\) change the colour complexity, or only the algorithms Takahashi et al. 2026?
Notes
Colour counts include the initial colour \(c_0\), as in Takahashi et al. 2026 and Hiraoka et al. 2026; Böckenhauer, Frei, Unger and Wehner count without it, so their 7 is 8 here. Restricted classes: five colours suffice for triangle-free graphs (Theorem 2 of the arXiv v2 of Takahashi et al. 2026) and for φ-free graphs, those in which, for every node \(v\) of degree at least four, each component of \(G - v\) contains at most two neighbours of \(v\); they include all graphs of maximum degree three and all cacti (Theorem 3 of Takahashi et al. 2026; the name is the paper's). Hiraoka, Imori, Takahashi and Sudo extend the five-colour algorithm to graphs whose blocks are cliques or triangle-free, with \(O(n\Delta)\) moves (Theorem 11), and show that this class is exactly where its cleanup conditions hold Hiraoka et al. 2026. All known results are for a single agent. Checked against the full texts; Hiraoka et al. 2026 is a preprint and its lower bound is computer-assisted.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
Branches from here
Recolourable nodes on cacti
Recolourable nodes on trees
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.