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.
Once-colourable nodes, any graph
verifiedIf a coloured node can never be recoloured, \(n\) colours are necessary and sufficient.
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: colour once
- Every node starts with the initial colour \(c_0\). The agent at \(v\) may change \(\psi(v)\) only while \(\psi(v) = c_0\); once \(v\) has a colour other than \(c_0\) it keeps it forever. This is the main model of Böckenhauer et al. 2023.
- 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.
What is known
- uniform algorithm: it must explore all graphs, \(n\) unknown (Theorem 4; stated as \(n-1\) without \(c_0\))
- for every \(n\) there is an \(n\)-node graph on which the algorithm uses \(n\) colours; the proof forces the agent along a path of a larger graph that it cannot tell from the small one
- also holds for bipartite graphs up to one colour: \(n-1\) (as summarised in Takahashi et al. 2026)
Results, in order of publication
Introductory and current best (Theorem 3, DepthFirstSearch): every newly visited node gets a colour larger than all its coloured neighbours, so the predecessor is always identifiable. Time not analysed.
Open questions
For graphs of circumference \(\mathrm{circ}(G) \le g\), close the gap between \(\min(2g-2, n)\) and \(\min(2g, n)\) colours Böckenhauer et al. 2023.
Notes
The driving parameter is the circumference \(\mathrm{circ}(G)\), the length of a longest cycle (their \(k\)): for graphs of circumference at most \(g\), \(\min(2g-2, n)\) colours are necessary and \(\min(2g, n)\) suffice, counting \(c_0\) (Theorems 8 and 9 of Böckenhauer et al. 2023). A special class can be much cheaper: squares of paths need only five colours although their circumference is maximal (Theorem 10, four without \(c_0\)). Checked against the full text.
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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Branches from here
Once-colourable nodes, \(n\) known
Once-colourable nodes on trees
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.