Universality and madericity of digraphs

• Grant number: 23/16755-2
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• Start date: September 01, 2024
• End date: August 31, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Orlando Lee
• Grantee: Caroline Aparecida de Paula Silva
• Supervisor: Frederic Havet
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: Institut National de Recherche en Informatique et en Automatique (INRIA Sophia Antipolis), France
• Associated to the scholarship: 22/03735-0 - alpha-Diperfect and chi-Diperfect Digraphs, BP.DR

Abstract

In problems of universality and madericity of digraphs we are interested in obtaining sufficient conditions for a digraph to contain a certain fixed subdigraph.Formally, for a digraph parameter $\gamma$, we say that a digraph $F$ is $\gamma$-universal if there is an integer $c = c(F)$ such that every digraph $D$ with $\gamma(D) \geq c$ contains $F$ as a subdigraph. Similarly, we say that $F$ is $\gamma$-maderian if there is $c$ such that every digraph $D$ with $\gamma(D) \geq c$ contains a subdivision of $F$ as a subdigraph.Several studies have been done on the universality and maderacity of digraphs, for example when $\gamma$ is the chromatic number, minimum out-degree, or average out-degree. Here, we are particularly interested when $\gamma$ is the (vertex)-chromatic number $\chi$. It is known that a digraph $F$ is $\chi$-universal (respectively, $\chi$-maderian) if and only if $F$ is an oriented forest. However, it is an open problem to determine what is the smallest $c$ for which every digraph $D$ with $\chi(D) \geq c$ contains an oriented tree $F$ as a subdigraph (respectively, as a subdivision); such a value $c$ is called the $\chi$-universality of $F$ (respectively, the $\chi$-madericity of $F$).The best upper bound known so far for these parameters is quadratic on the order of $F$, but this value is not tight.In this project, we intend to investigate these problems with the aim of obtaining a tighter upper bounds for the $\chi$-universality or the $\chi$-madericity of an oriented tree.