Path packing and partial coloring in digraphs.

• Grant number: 24/14743-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: January 01, 2025
• End date: December 31, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Orlando Lee
• Grantee: Marcos Paulo Evers Cordeiro
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In this project, we aim to study some problems of a theoretical nature. For an arbitrary digraph D, the relationship between path partitions and packings of stable sets (partial colorings), as well as the relationship between partitions into stable sets (coloring) and path packing, is not yet fully understood. Two conjectures by Linial attempt to capture these two relationships, respectively. The project will focus on the second problem, but we present both problems as they are closely related through a duality relationship.