Coloring temporal graphs

摘要

A temporal graph is a pair (G,λ) where G is a simple graph and λ is a function assigning to each edge time labels telling at which snapshots each edge is active. As recently defined by Mertzios, Molter and Zamaraev (2021), a temporal coloring of (G,λ) is a sequence of colorings of the vertices of the snapshots such that each edge is properly colored at least once. We first focus on t-persistent and t-occurrent temporal graphs. The former (resp. the latter) are temporal graphs where each edge of G stays active for at least t consecutive (resp. not-necessarily consecutive) snapshots. We study which values of t make the problem polynomial-time solvable. We also investigate the complexity of the problem when restricted to temporal graphs (G,λ) such that G has bounded treewidth.