Now showing items 1-10 of 10

• 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 ...
• b-Coloring Parameterized by Clique-Width ﻿

(Journal article; Peer reviewed, 2023)
We provide a polynomial-time algorithm for b- Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by ...
• 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 ...
• On the maximum number of edges in planar graphs of bounded degree and matching number ﻿

(Journal article; Peer reviewed, 2023)
We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.
• 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 ...
• Reducing the domination number of graphs via edge contractions and vertex deletions ﻿

(Journal article; Peer reviewed, 2021)
In this work, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k>0? We show that for k=1 (resp. k=2), the ...
• 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 ...
• Well-partitioned chordal graphs ﻿

(Journal article; Peer reviewed, 2022)
We introduce a new subclass of chordal graphs that generalizes the class of split graphs, which we call well-partitioned chordal graphs. A connected graph G is a well-partitioned chordal graph if there exist a partition P ...