2026-07-21T14:18:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19925 2024-05-29T09:43:30Z ddc:004 open_access

Computational Complexity of Matching Match Puzzle Iburi, Yuki Uehara, Ryuhei Graph coloring Matching Match puzzle NP-complete polynomial-time solvable Various forms of graph coloring problems have been studied over the years in the society of graph theory. Recently, some original puzzles are popularized in Japanese 100-yen shops, and one of them can be formalized as a graph coloring problem in a natural way. However, this natural graph coloring problem has not been investigated in the context of the graph theory. In this paper, we investigate this puzzle as a graph coloring problem. We first prove that this graph coloring problem is NP-complete even when the graph is restricted to a path or a spider. In these cases, diameter of the graphs seems to play an important role for its difficulty. We then show that the problem can be solved in polynomial time when the graph is restricted to some graph classes of constant diameter. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuki Iburi and Ryuhei Uehara 2024 Is Part Of LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2024.17 urn:nbn:de:0030-drops-199251 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.17 eng https://creativecommons.org/licenses/by/4.0/legalcode