Harmonious colourings of temporal matchings
Duncan Adamson · Theoretical Computer Science · 2025
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 -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 -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 , or when and . We further show that this problem is inapproximable for and an unbounded value of k , and that the problem of determining the temporal harmonious chromatic number of a -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 classes of -temporal matchings, paths, and cycles.