J. Araújo

activity

20152023

collaborators

9 papers

cs.CC2023

The iteration time and the general position number in graph convexities

Julio Araujo, Mitre C. Dourado, Fábio Protti +1

In this paper, we study two graph convexity parameters: iteration time and general position number. The iteration time was defined in 1981 in the geodesic convexity, but its comput…

cs.CC2020

On the proper orientation number of chordal graphs

Julio Araujo, Alexandre Cezar, Carlos V. G. C. Lima +2

An orientation $D$ of a graph $G = (V, E)$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same end vertices. For each $v \in V(…

math.CO2019

Hull and Geodetic Numbers for Some Classes of Oriented Graphs

Julio C. S. Araujo, Pedro S. M. Arraes

Let $D$ be an orientation of a simple graph. Given $u, v \in V (D)$ , a directed shortest $(u, v)$ -path is a $(u, v)$ -geodesic. $S \subseteq V (D)$ is convex if, for every $u, v \in S$ , th…

cs.DS2018

Dual parameterization of Weighted Coloring

Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima +3

Given a graph $G$ , a proper $k$ -coloring of $G$ is a partition $c = (S_{i})_{i \in [1, k]}$ of $V (G)$ into $k$ stable sets $S_{1}, \dots, S_{k}$ . Given a weight function $w: V(G) \to \ma…

cs.DS2018

Weighted proper orientations of trees and graphs of bounded treewidth

Júlio Araújo, Cláudia Linhares Sales, Ignasi Sau +1

Given a simple graph $G$ , a weight function $w : E (G) \to N ∖ {0}$ , and an orientation $D$ of $G$ , we define $μ^{-} (D) = max_{v \in V (G)} w_{D}^{-} (v)$ , where $w…

cs.DS2017

On the complexity of finding internally vertex-disjoint long directed paths

Júlio Araújo, Victor A. Campos, Ana Karolinna Maia +2

For two positive integers $k$ and $ℓ$ , a $(k \times ℓ)$ -spindle is the union of $k$ pairwise internally vertex-disjoint directed paths with $ℓ$ arcs between two vertices $…