Browsing Faculty of Mathematics and Natural Sciences by Journals "Discrete Applied Mathematics"

Now showing items 1-4 of 4

    • Cyclability in graph classes 

      Crespelle, Christophe Dominique; Golovach, Petr (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 

      Jaffke, Lars; Jansen, Bart Maarten Paul (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 

      Samer, Phillippe; Haugland, Dag (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 

      Samer, Phillippe; Moura, Phablo F S (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, ...