How to Color Temporal Graphs to Ensure Proper Transitions
Allen Ibiapina, Minh Hang Nguyen, Mikaël Rabie, Cléophée Robin · 2025
Read How to Color Temporal Graphs to Ensure Proper Transitions by Allen Ibiapina, Minh Hang Nguyen, Mikaël Rabie, Cléophée Robin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-10207.txt.
Introduction
Allen Ibiapina, Minh Hang Nguyen, Mikaël Rabie, and Cléophée Robin define graph coloring for temporal graphs, in a paper from twenty twenty-five. Classical coloring forbids adjacent vertices sharing a color. In dynamic graphs, that notion is ambiguous across time steps. Their coloring must stay proper at every step, including during transitions between snapshots.
Compatibility between consecutive snapshots ensures properness survives each transition. The minimum colors needed is the graph's temporal chromatic number. The authors give lower and upper bounds for the general case. Specific classes receive closer treatment, including trees and graphs of bounded degree or degeneracy. They also study graphs growing by one edge swap per step. Results hold even online, when future snapshots are unknown while coloring proceeds.
Catalog record
| CREATOR | Allen Ibiapina, Minh Hang Nguyen, Mikaël Rabie, Cléophée Robin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-10207
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
How to Color Temporal Graphs to Ensure Proper Transitions Allen Ibiapina, Minh Hang Nguyen, Mikaël Rabie, Cléophée Robin Abstract Graph Coloring consists in assigning colors to vertices ensuring that two adjacent vertices do not have the same color. In dynamic graphs, this notion is not well defined, as we need to decide if different colors for adjacent vertices must happen all the time or not, and how to go from a coloring in one time to the next one. In this paper, we define a coloring notion for Temporal Graphs where at each step, the coloring must be proper. It uses a notion of compatibility between two consecutive snapshots that implies that the coloring stays proper while the transition happens. Given a graph, the minimum number of colors needed to ensure that such coloring exists is the Temporal Chromatic Number of this graph. With those notions, we provide some lower and upper bounds for the temporal chromatic number in the general case. We then dive into some specific classes of graphs such as trees, graphs with bounded degree or bounded degeneracy. Finally, we consider temporal graphs where grow pace is one, that is, a single edge can be added and a single other one can be removed between two time steps. In that case, we consider bipartite and bounded degree graphs. Even though the problem is defined with full knowledge of the temporal graph, our results also work in the case where future snapshots are given online: we need to choose the coloring of the next snapshot after having computed the current one, not knowing what will come later. Université Paris Cité, CNRS, IRIF, F-75013, Paris, France and [email protected]://orcid.org/0000-0002-6584-7718 Université Paris Cité, CNRS, IRIF, F-75013, Paris, France and https://www.irif.fr/~mhnguyen/ [email protected]://orcid.org/0009-0008-2391-029X Université Paris Cité, CNRS, IRIF, F-75013, Paris, France and https://www.irif.fr/~rabie/ [email protected]://orcid.org/0000-0001-6782-7625 Université Paris Cité, CNRS, IRIF, F-75013, Paris, France and https://orcid.org/0000-0002-1825-0097 The authors thank the members of ANR Tempogral and GrR for their insightful inputs, in particular Marthe Bonamy for her contribution with Theorem 7 . This work was supported by the French ANR project TEMPOGRAL (ANR-22-CE48-0001). The second author has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No 945332. ccs Mathematics of Computing -¿ Discrete Mathematics -¿ Graph Theory-¿ Graph coloring. keywords Temporal Graphs, Coloring. † † runningauthor: A. Ibiapina, M. H. Nguyen, M. Rabie and C. Robin † † copyright: Allen Ibiapina, Minh Hang Nguyen, Mikael Rabie, Cleophee Robin 1 Introduction 1.1 Motivation The Vertex Coloring Problem in (static) graphs is a well-studied problem. The goal is to assign colors to the vertices such that two adjacent vertices have different colors. The usual questions concern the complexity of finding a coloring with few colors, and the Chromatic Number of a graph that is the minimum number of colors needed to ensure the existence of a coloring. The coloring can represent a radio frequency allocation: if two transmitter are too close together (i.e. neighbors in the graph), they cannot use the same frequency, because their messages would collide. In Temporal Graphs , or dynamic networks, changes occur over time. More precisely, at each time step, the set of edges between the vertices evolves. In this work, the time will be discretized. This can be done by considering step times when changes occur. The graph with its set of edges at a fixed time is called a Snapshot . To illustrate, temporal graphs can model sensors on a system. At each time step, if two sensors are close enough, an edge between the corresponding vertices appears in the graph. A frequency mapping must ensure that sensors too close to each other must use different wave lengths. This can be modeled by assigning a color to every vertex for every time step such that two vertices adjacent in some snapshot must have different colors in this snapshot. We want to ensure some robustness on the coloring such that, through each transition between two snapshots, no collision can happen. An immediate solution can be to use a proper coloring of the union of all the edges through time. With such assignment, every pair of vertices that are adjacent in at least one snapshot have different colors at any time. However, this solution can be expensive considering the number of colors used. Indeed, if every possible edge appears at least once, one different color for every vertex will be used. It is possible to add some constraints on the considered graphs to ensure a low chromatic number for each snapshot. For example, a temporal graph such that all snapshot is a tree ensure that every snapshot is 2-colorable. Such constraint directly implies that it is possible to use less colors. In this case, it implies that nodes must change color over time in order to take into account their future neighborhood while relax constraints from previous neighbors. Through a transition between two snapshots, three operations can occur: the removal of some edges, the addition of some edges and the color change for some vertices. We consider that those transformations are not done simultaneously but one after the other without any information on the order. More precisely, given two vertices that are adjacent in some snapshot and become non-adjacent in the next snapshot, it is not possible for them to have the same color in the next snapshot. This is because their colors might change before the edge is removed. Another consequence is that two vertices that are adjacent cannot exchange their color as one will have to do the change before the other and between the two, both vertices are still adjacent but have the same colors. Dealing with those transformation motivates the notion of Compatibility between two snapshots: for any possible sequence of transformations between two snapshots, the coloring have to stay proper at any time. A Temporal Coloring of a temporal graph is a proper coloring of every snapshot that respects the compatibility constraint. The Temporal Chromatic Number of a temporal graph \cal G , denoted \chi^{t}({\cal G}) , is the minimum number of colors needed for a temporal coloring of the graph. We show how to relate this number to the chromatic number of each snapshot and the chromatic number of the union (or Smashing ) of three consecutive snapshots. As we have no control over the evolution of the graph between successive snapshots, we may have massive changes. However, in systems of sensors, not so many changes can occur between two snapshots. We introduce a notion to limit the number of edges that can be added or removed between time steps. The Grow Pace of a temporal graph is the maximum number of edges added and removed between two snapshots. For example, if a temporal graph has grow pace 1, that means that, between every consecutive snapshot, at most one edge is added and at most one edge is deleted. In general the grow pace is unbounded. We study and provide temporal chromatic number bounds for temporal graphs with grow pace 1. In particular, we get different temporal chromatic numbers for graphs with grow pace 1 compared to temporal graphs without limitations. A question arising is, given a