2026-07-22T09:10:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19882 2024-05-31T08:33:43Z ddc:004 open_access

Harmonious Colourings of Temporal Matchings Adamson, Duncan Temporal Graphs Harmonious Colouring NP-Completeness Graph colouring is a fundamental problem in computer science, with a large body of research dedicated to both the general colouring problem and restricted cases. Harmonious colourings are one such restriction, where each edge must contain a globally unique pair of colours, i.e. if an edge connects a vertex coloured x with a vertex coloured y, then no other pair of connected vertices can be coloured x and y. Finding such a colouring in the traditional graph setting is known to be NP-hard, even in trees. This paper considers the generalisation of harmonious colourings to Temporal Graphs, specifically (k,t)-Temporal matchings, a class of temporal graphs where the underlying graph is a matching (a collection of disconnected components containing pairs of vertices), each edge can appear in at most t timesteps, and each timestep can contain at most k other edges. We provide a complete overview of the complexity landscape of finding temporal harmonious colourings for (k,t)-matchings. We show that finding a Temporal Harmonious Colouring, a colouring that is harmonious in each timestep, is NP-hard for (k,t)-Temporal Matchings when k ≥ 4, t ≥ 2, or when k ≥ 2 and t ≥ 3. We further show that this problem is inapproximable for t ≥ 2 and an unbounded value of k, and that the problem of determining the temporal harmonious chromatic number of a (2,3)-temporal matching can be determined in linear time. Finally, we strengthen this result by a set of upper and lower bounds of the temporal harmonious chromatic number both for individual temporal matchings and for the class of (k, t)-temporal matchings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Duncan Adamson 2024 Is Part Of LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2024.4 urn:nbn:de:0030-drops-198823 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.4 eng https://creativecommons.org/licenses/by/4.0/legalcode