Algorithmic and structural aspects of covering and packing problems on graphs
Orthogonality of packings of paths and independent sets partitions on bipartite gr...
| Grant number: | 20/06116-4 |
| Support Opportunities: | Scholarships in Brazil - Master |
| Start date: | January 01, 2021 |
| End date: | February 28, 2022 |
| 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 Let $D$ be a digraph. A coloring $\cal{C}$ and a path $P$ of $D$ are \emph{orthogonal} if $P$ contains exactly one vertex of each color class in $\cal{C}$. In 1982, Berge defined the class of $\chi$-diperfect digraphs. A digraph $D$ is $\chi$-diperfect if for every optimal coloring $\cal{C}$ of $D$ there exists a path $P$ orthogonal to $\cal{C}$ and this property holds for every induced subdigraph of $D$. Berge also showed that every perfect digraph is $\chi$-diperfect, as well as every symmetric digraph. Let $D$ be a super-orientation of an odd cycle $C=(x_1,x_2,\ldots,x_{2\ell+1},x_1)$ and let $P=(x_i,\ldots,x_j)$ be a subpath of $C$. The subdigraph $D[V(P)]$ is a \emph{sector} if each of $x_i$ and $x_j$ is a source or a sink in $D$; a sector is \emph{odd} if $P$ has odd length. We say that $D$ is a \emph{conflicting odd cycle} if it contains at least two arc-disjoint odd sectors. It can be shown that a super-orientation of an odd cycle is $\chi$-diperfect, if and only if, it is not a conflicting odd cycle. From this we have that a $\chi$-diperfect digraph cannot contain a conflicting odd cycle as an induced subdigraph. The converse, however, is not true; Berge showed that there is an orientation of the complement of a cycle with seven vertices that is free of induced conflicting odd cycles and is not $\chi$-diperfect. It is desirable to obtain a characterization of $\chi$-diperfect digraphs, but this may be a very difficult problem and not very likely to be solved in a near future. In this project we intend to start the investigation of this problem through two approaches. The first is to attempt to find a characterization of which super-orientations of complement of odd cycles are $\chi$-diperfect. The second is to consider some specific classes of digraphs to try to discover which elements in such classes are $\chi$-diperfect. (AU) | |
| News published in Agência FAPESP Newsletter about the scholarship: | |
| More itemsLess items | |
| TITULO | |
| Articles published in other media outlets ( ): | |
| More itemsLess items | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |