4 papers · 1 filter
Extension of the Gyárfás-Sumner conjecture to signed graphs
Guillaume Aubian, Allen Ibiapina, Luis Kuffner +4
The balanced chromatic number of a signed graph G is the minimum number of balanced sets that cover all vertices of G. Studying structural conditions which imply bounds on the bala…
How to Color Temporal Graphs to Ensure Proper Transitions
Allen Ibiapina, Minh Hang Nguyen, Mikaël Rabie +1
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 ne…
Temporal Cycle Detection and Acyclic Temporization
Davi de Andrade, Júlio Araújo, Allen Ibiapina +3
In directed graphs, a cycle can be seen as a structure that allows its vertices to loop back to themselves, or as a structure that allows pairs of vertices to reach each other thro…
Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
Guillaume Aubian, Filippo Brunelli, Feodor F Dragan +4
Temporal graphs arise when modeling interactions that evolve over time. They usually come in several flavors, depending on the number of parameters used to describe the temporal as…