DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2025.32

Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors

Authors: Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract

Recently, Böckenhauer, Frei, Unger, and Wehner (SIROCCO 2023) introduced a novel variant of the graph exploration problem in which a single memoryless agent must visit all nodes of an unknown, undirected, and connected graph before returning to its starting node. Unlike the standard model for mobile agents, edges are not labeled with port numbers. Instead, the agent can color its current node and observe the color of each neighboring node. To move, it specifies a target color and then moves to an adversarially chosen neighbor of that color. They analyzed the minimum number of colors required for successful exploration and proposed an elegant algorithm that enables the agent to explore an arbitrary graph using only eight colors. In this paper, we present a novel graph exploration algorithm that requires only six colors. Furthermore, we prove that five colors are sufficient if we consider only a restricted class of graphs, which we call the φ-free graphs, a class that includes every graph with maximum degree at most three and every cactus.

Cite as

Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo. Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{takahashi_et_al:LIPIcs.OPODIS.2025.32,
  author =	{Takahashi, Shota and Kanaya, Haruki and Hiraoka, Shoma and Eguchi, Ryota and Sudo, Yuichi},
  title =	{{Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.32},
  URN =		{urn:nbn:de:0030-drops-252052},
  doi =		{10.4230/LIPIcs.OPODIS.2025.32},
  annote =	{Keywords: mobile agents, recolorable graphs, graph exploration}
}

Search Results

Documents authored by Takahashi, Shota

Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors

Abstract

Cite as

Thanks for your feedback!

Could not send message