Browsing Department of Informatics by Journals "Discrete Applied Mathematics"
Now showing items 1-4 of 4
-
Cyclability in graph classes
(Journal article; Peer reviewed, 2022)A subset T ⊆ V(G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T, and for a positive integer k, a graph G is k-cyclable if every set of vertices of size at most k is cyclable. ... -
Fine-grained parameterized complexity analysis of graph coloring problems
(Journal article; Peer reviewed, 2023)The q-Coloring problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a fine-grained analysis of the complexity of q- Coloring with respect to a hierarchy of structural ... -
Fixed cardinality stable sets
(Journal article; Peer reviewed, 2021)Given an undirected graph G=(V,E) and a positive integer k in {1, ..., |V|}, we initiate the combinatorial study of stable sets of cardinality exactly k in G. Our aim is to instigate the polyhedral investigation of the ... -
Polyhedral approach to weighted connected matchings in general graphs
(Journal article; Peer reviewed, 2024)A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G. While finding a connected matching of maximum cardinality is a well-solved problem, ...