Orthogonality of packings of paths and independent sets partitions on bipartite graphs

• Grant number: 18/11462-9
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: November 01, 2018
• End date: August 31, 2019
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Candida Nunes da Silva
• Grantee: Caroline Aparecida de Paula Silva
• Host Institution: Centro de Ciências em Gestão e Tecnologia (CCGT). Universidade Federal de São Carlos (UFSCAR). Campus de Sorocaba. Sorocaba , SP, Brazil

Abstract

In 1982, Berge proposed a conjecture on directed graphs which relates directed path partitions and collections of disjoint independent sets. Berge also showed the validity of his conjecture for certain classes of graphs. In face of his observations, it is a natural question whether one similar relation exists when the roles of paths and independent sets are switched. The natural question is thus whether there is a relation between independent sets partitions (or vertex colorings) and collections of directed paths. Such question became known as the Dual version of Berge's Conjecture. We say a vertex coloring C and a set P of k directed paths for an integer k are orthogonal if each color class intersects the highest possible number of paths in P, that is, every vertex in the color class is in some path of P if the class has cardinality at most k or at least one vertex of the color class is in each path otherwise. This conjecture is known to be false in general. However, the known counterexamples have odd cycles and no bipartite counterexample for the conjecture could be found in the literature. Therefore, the purpose of this project is to investigate the validity of the Dual Version of Berge's Conjecture for the class of bipartite digraphs. Including bipartite graphs $ C $ color class intersects the largest number of possible paths in $ P $, that is, the intersection is the whole class if it has cardinality less than $ k $ or $ k $ otherwise. Such a conjecture is false for digraphs in general and exhibits counterexample. However, the known counterexamples have odd cycles and there is no record in the literature of having been asked whether the conjecture would be valid for digraphs without odd cycles, ie, bipartite digraphs. Thus, this project intends to study in a deeper way the relation between coloration and collections of paths, and to verify if the Berge Dual Conjecture is true for two-part digraphs.