Partition Problems for Directed and Undirected Graphs

This thesis introduces and explores several partition problems in both directed and undirected graphs.

One of the most well-known partition problems in graph theory is the maximum cut problem. In a weighted graph (digraph, respectively) $G$, a cut (directed cut, respectively) is a bipartition (an ordered bipartition, respectively) $(X, Y)$ of its vertex set. The weight of a cut is defined as the sum of the weights of the edges (arcs, respectively) between $X$ and $Y$ (from $X$ to $Y$, respectively). A maximum weight cut (maximum weight directed cut, respectively) is a cut whose weight is at least as large as that of any other cut. In Chapters 3, 4 and 5, we investigate the maximum weight cut and one of its variants, the maximum weight bisection problem, where a bisection is a cut $(X, Y)$ satisfying $||X| - |Y|| \leq 1$. In particular, the most technical part in Chapter 3 is devoted to the maximum weight directed cut problem for acyclic digraphs (i.e., directed graphs without directed cycles). In Chapters 4 and 5, we examine the maximum weight bisection problem for graphs with bounded degrees and specific forbidden subgraphs, respectively.

A well-known class of partition problems involves decomposing graphs into vertex-disjoint subgraphs while maintaining certain degree constraints. Several results have shown that graphs with high minimum degree can be partitioned into vertex-disjoint subgraphs with relatively large minimum degree. However, proving analogous results for digraphs is significantly more challenging. One prominent open problem in this area is the Bermond–Thomassen conjecture, which states that every digraph with minimum out-degree at least $2k-1$ can be partitioned into $k$ vertex-disjoint subgraphs, each having a minimum out-degree of at least 1. In Chapter 6, we make progress on this conjecture by proving it for a new class of digraphs.

Another fundamental problem in graph theory is the minimum feedback arc set problem, which has numerous applications. In Chapter 7, we seek improved bounds for the minimum feedback arc sets of sparse weighted oriented graphs. To this end, we initiate the study of partitioning the arc set of a digraph into the maximum possible number of feedback arc sets, providing new insights into this problem.