$\alpha$-Diperfect and $\chi$-Diperfect Digraphs
Palestra
Resumo
Em 1982, Berge definiu duas classes de digrafos com o objetivo de identificar propriedades relacionadas à relação entre conjuntos independentes e caminhos em digrafos. A primeira delas é a classe dos digrafos $\alpha$-diperfeitos. Um digrafo $D$ é $\alpha$-diperfeito se, para todo conjunto independente máximo $S$ de $D$, existe uma partição de caminhos $\mathcal{P}$ de $D$ tal que todo caminho em $\mathcal{P}$ contém exatamente um vértice de $S$, e essa propriedade é válida para todo subdigrafo induzido de $D$. A segunda é a classe dos digrafos $\chi$-diperfeitos. Um digrafo $D$ é $\chi$-diperfeito se, para toda coloração mínima $\mathcal{S}$ de $D$, existe um caminho $P$ de $D$ contendo exatamente um vértice de cada classe de cor de $\mathcal{S}$, e essa propriedade é válida para todo subdigrafo induzido de $D$. Nem todo digrafo é $\alpha$-diperfeito (respectivamente, $\chi$-diperfeito), e o objetivo central nessa área de pesquisa é o mesmo para ambas as classes de digrafos: caracterizar cada classe em termos de subdigrafos induzidos proibidos. Nesta palestra, apresentaremos alguns resultados e problemas em aberto relacionados a essas duas classes de digrafos.
Materiais