Ignasi Sau

activity

20082025

most citedAn FPT 2-Approximation for Tree-Cut Decomposition

23 citations · 60 across the 50 of their papers we have counts for

collaborators

Showing 2018Show all

4 papers · 1 filter

math.CO2018

Counting Gallai 3-colorings of complete graphs

Josefran de Oliveira Bastos, Fabricio Siqueira Benevides, Guilherme Oliveira Mota +1

An edge coloring of the n-vertex complete graph K_n is a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle whose edges are colored with three distinc…

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

Maximum cuts in edge-colored graphs

Luerbio Faria, Sulamita Klein, Ignasi Sau +2

The input of the Maximum Colored Cut problem consists of a graph $G = (V, E)$ with an edge-coloring $c : E \to {1, 2, 3, \dots, p}$ and a positive integer $k$ , and the question is wheth…

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…