Deterministic labelling of graph vertices by walking agent

This paper is devoted to the problem of on-line labelling of graph vertices by walking agent so that all vertices in the neighbourhood of the current vertex have different labels (i.e. deterministic labelling). This problem arises in the navigation of mobile robots using topological maps of an environment. Here, a method for deterministic labelling is proposed for an agent of two types differing by the size of the observed neighbourhood of the current vertex.