Back
phd_Luckef_A.pdf
Doctoral thesis

Matching cut and variants in graphs of bounded radius, bounded diameter and h-free graphs

DOKPE

  • Fribourg (Switzerland) : Université de Fribourg, 2024

1 ressource en ligne (vii, 111 pages) ; 1 fichier pdf

PhD: Université de Fribourg (Suisse), 25.07.2024

graphs
bounded radius
bounded diameter
h-free graphs
English A matching in a graph G = (V, E) is a set M ⊆ E, such that no two edges in M share an endvertex. An edge cut in G is a set of edges C ⊆ E, such that we can partition V into two non-empty sets R and B, where C is the set of edges with one endvertex in R and one in B. A matching cut is a set of edges M ⊆ E which is both a matching and an edge cut. In this thesis, we consider the decision problems Matching Cut, its variants Disconnected Perfect Matching and Perfect Matching Cut, as well as its generalisation d-Cut. We give polynomial time algorithms and NP-completeness results for certain graph classes, including H-free graphs, for some graphs H, and graphs of bounded radius and diameter. In particular, we solve a 20-year old open problem by showing the NP-completeness of Matching Cut for graphs of high girth. We also consider the maximisation version Maximum Matching Cut, where we ask for a matching cut of maximum size, that is with the maximum number of edges in the matching cut. For this variant we give a complexity dichotomy for graphs of bounded radius, bounded diameter, H-free graphs and bipartite graphs of bounded radius and diameter. We conclude with a comparison of all variants, which allows to identify interesting open problems.
Faculty
Faculté des sciences et de médecine
Department
Département d'Informatique
Language
  • English
Notes
  • Bibliographie
License
CC BY
Open access status
diamond
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/336368
Statistics
Document views: 32 File downloads:
  • phd_Luckef_A.pdf: 28