4 citations · 12 across the 12 of their papers we have counts for
4 papers · 1 filter
Algorithms for the rainbow vertex coloring problem on graph classes
Paloma T. Lima, Erik Jan van Leeuwen, Marieke van der Wegen
Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow…
Blocking dominating sets for -free graphs via edge contractions
Esther Galby, Paloma T. Lima, Bernard Ries
In this paper, we consider the following problem: given a connected graph , can we reduce the domination number of by one by using only one edge contraction? We show that th…
On the Parameterized Complexity of -Edge Colouring
Esther Galby, Paloma T. Lima, Daniël Paulusma +1
For every fixed integer , we prove that -Edge Colouring is fixed-parameter-tractable when parameterized by the number of vertices of maximum degree.
Transversals of Longest Paths
Márcia R. Cerioli, Cristina G. Fernandes, Renzo Gómez +2
Let $\lpt(G)$ be the minimum cardinality of a set of vertices that intersects all longest paths in a graph . Let be the size of a maximum clique in , and $\tw(G)$ be t…