Coloring temporal graphs

Abstract 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.