Now showing items 1-6 of 6

• #### Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes ﻿

(Journal article; Peer reviewed, 2020)
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 vertex path between every pair of its ...
• #### A complexity dichotomy for critical values of the b-chromatic number of graphs ﻿

(Journal article; Peer reviewed, 2020)
A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has ...
• #### A complexity dichotomy for critical values of the b-chromatic number of graphs ﻿

(Peer reviewed; Journal article, 2019-08-20)
A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has ...
• #### Reducing Graph Transversals via Edge Contractions ﻿

(Journal article; Peer reviewed, 2020)
For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least ...
• #### Structural parameterizations of clique coloring ﻿

(Journal article; Peer reviewed, 2020)
A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether ...
• #### Transversals of longest paths ﻿

(Journal article; Peer reviewed, 2020-03)
Let lpt(G) be the minimum cardinality of a transversal of longest paths in G, that is, a set of vertices that intersects all longest paths in a graph G. There are several results in the literature bounding the value of ...