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.
Coloring temporal graphs / Marino A.; Silva A.. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - ELETTRONICO. - 123:(2022), pp. 171-185. [10.1016/j.jcss.2021.08.004]
Coloring temporal graphs
Marino A.;Silva A.
2022
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.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.