Browsing Faculty of Mathematics and Natural Sciences by Journals "Discrete Applied Mathematics"
Now showing items 14 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 kcyclable if every set of vertices of size at most k is cyclable. ... 
Finegrained parameterized complexity analysis of graph coloring problems
(Journal article; Peer reviewed, 2023)The qColoring problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a finegrained 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 wellsolved problem, ...