J. Araújo

activity

20162020

collaborators

7 papers

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 $…

cs.DS2017

Ruling out FPT algorithms for Weighted Coloring on forests

Júlio Araújo, Julien Baste, Ignasi Sau

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…