11 papers
An orthogonality inequality in and the double-cap conjecture
Allen Ibiapina, Carlos Gomes, Alan Pio +2
The orthogonal neighborhood of a set in real projective space is the union of the hyperplanes perpendicular to its points. We prove that caps minimize neighborhood measure among me…
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…
Snapshot disjointness in temporal graphs
Allen Ibiapina, Ana Silva
In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walks disjointness were proposed over the years, and the val…
Mengerian graphs: characterization and recognition
Allen Ibiapina, Ana Silva
A temporal graph is a graph that changes with time. More specifically, it is a pair where is a graph and is a function on the edges of that describe…
Menger's Theorem for Temporal Paths (Not Walks)
Allen Ibiapina, Raul Lopes, Andrea Marino +1
A (directed) temporal graph is a (directed) graph whose edges are available only at specific times during its (discretized) lifetime . In this setting, we ask that walks respect…
Coloring Problems on Bipartite Graphs of Small Diameter
Victor A. Campos, Guilherme C. M. Gomes, Allen Ibiapina +3
We investigate a number of coloring problems restricted to bipartite graphs with bounded diameter. First, we investigate the -List Coloring, List -Coloring, and -Precolori…
On Orthogonal Vector Edge Coloring
Ana Silva, Allen Ibiapina
Given a graph and a positive integer , an orthogonal vector -coloring of is an assignment of vectors of to in such a way that adjacent verti…
b-continuity and Partial Grundy Coloring of graphs with large girth
Allen Ibiapina, Ana Silva
A b-coloring of a graph is a proper coloring such that each color class has at least one vertex which is adjacent to each other color class. The b-spectrum of is the set $S_{b}…