Partition problems in graphs and digraphs

Abstract

This is the research project for the postdoctoral fellowship of Maycon Sambinelli, to be carried out under the supervision of Yoshiko Wakabayashi, at the Instituto de Matemática e Estatística of the University of São Paulo. This project addresses topics on structural graph theory, more specifically, classical partition problems in graphs and digraphs. We plan to investigate problems on vertex-partition and edge-partition. As an example, we mention a problem proposed by Linial in 1981. Let D be a digraph, k a positive integer, P a collection of vertex-disjoint paths which covers V(D) and minimizes \pi_k(D) = \sum_{P_i \in P} min{|V(P_i)|, k}, and let C be a collection of at most k disjoint stable sets which maximize \chi_k(D) = \sum_{C_i \in C} |C_i|. Prove that the relation \pi_k(D) \leq \alpha_k(D) holds for every digraph D. As an example of a problem on edge-partition, we mention the problem of verifying whether it is always possible to cover the edges of a given n-vertex graph G using at most (n + 1)/2 edge-disjoint paths. This upper bound was conjectured by Gallai in the late sixties, and has been proved for some classes of graphs. We expect to expand such classes, and also to contribute with new proof techniques to advance the state of the art of the field. (AU)