V. D. dos Santos

activity

20182022

collaborators

4 papers

cs.DS2022

Reducing the Vertex Cover Number via Edge Contractions

Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau +2

The CONTRACTION(vc) problem takes as input a graph $G$ on $n$ vertices and two integers $k$ and $d$ , and asks whether one can contract at most $k$ edges to reduce the size of a min…

cs.DS2020

On structural parameterizations of the selective coloring problem

Guilherme C. M. Gomes, Vinicius F. dos Santos

In the Selective Coloring problem, we are given an integer $k$ , a graph $G$ , and a partition of $V (G)$ into $p$ parts, and the goal is to decide whether or not we can pick exactly…

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.DM2018

Characterization by forbidden induced subgraphs of some subclasses of chordal graphs

Sérgio H. Nogueira, Vinicius F. dos Santos

Chordal graphs are the graphs in which every cycle of length at least four has a chord. A set $S$ is a vertex separator for vertices $a$ and $b$ if the removal of $S$ of the graph…