Advanced search
Start date
Betweenand

alpha-Diperfect and chi-Diperfect Digraphs

Grant number: 22/03735-0
Support Opportunities:Scholarships in Brazil - Doctorate
Effective date (Start): December 01, 2022
Effective date (End): February 28, 2026
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Orlando Lee
Grantee:Caroline Aparecida de Paula Silva
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Associated research grant:15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

In 1982, Berge defined two classes of digraphs in order to identify properties on the relation between stable sets and paths in digraphs. The first class that Berge defined is the class of $\alpha$-diperfect digraphs. A digraph $D$ is $\alpha$-diperfect if every induced subdigraph $D'$ of $D$ satisfies the following property: for every maximum stable set $S$ of $D'$ there is a path partition $\mathcal{P}$ of $D'$ such that every $P \in \mathcal{P}$ contains exactly one vertex of $S$. The second class that Berge defined is the class of $\chi$-diperfect digraphs. A digraph $D$ is $\chi$-diperfect if every induced subdigraph $D'$ of $D$ satisfies the following property: for every minimum coloring $\mathcal{C}$ of $D'$ there is a path $P$ of $D'$ containing exactly one vertex of each color class of $\mathcal{C}$. The ultimate goal in the research area is to obtain a characterization of $\alpha$-diperfect digraphs and of $\chi$-diperfect digraphs in terms of forbidden induced subdigraphs, but this may be a very difficult problem and not likely to be solved in a near future. In this project, we intend to obtain results towards this goal by investigating structural properties of these classes of digraphs and considering specific families of digraphs to try to discover which elements in such families are $\alpha$-diperfect or $\chi$-diperfect.The ultimate goal of this research area would be to obtain a characterizationof \chi-diperfect digraphs in terms of forbidden subdigraphs, but this may bea very difficult problem and not likely to be solved in a near future.In 2022, Silva, Silva and Lee presented a characterization of \chi-diperfect super-orientations of odd cycles and of complements of odd cycles with at least five vertices. Moreover, they gave examples of minimal non-\chi-diperfect digraphs that were not yet known. Such obstructions are digraphs that have stability number two or three. In this project we intend to address this problem through two approaches. The first one is to investigate the obstructions with stability number two and try to identify structural properties that help us to deal with obstructions with stability number greater than two. The second one is to consider some specific classes of digraphs to try to discover which elements in such classes are \chi-diperfect.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Please report errors in scientific publications list using this form.