Busca avançada
Ano de início
Entree

Ortogonalidade entre empacotamento de caminhos e partições em conjuntos independentes para dígrafos bipartidos

Processo: 18/11462-9
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de novembro de 2018
Vigência (Término): 31 de agosto de 2019
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Candida Nunes da Silva
Beneficiário:Caroline Aparecida de Paula Silva
Instituição-sede: Centro de Ciências em Gestão e Tecnologia (CCGT). Universidade Federal de São Carlos (UFSCAR). Campus de Sorocaba. Sorocaba , SP, Brasil
Assunto(s):Teoria dos grafos   Empacotamento e cobertura   Grafos aleatórios   Coloração   Funções ortogonais

Resumo

Em 1982, Berge propôs uma conjectura sobre grafos direcionados que relaciona partições em caminhos direcionados com coleções de conjuntos independentes disjuntos. Berge ainda mostrou que sua conjectura era válida para certas classes de grafos. Diante dos resultados por ele observados, é natural questionar-se se a relação continuaria a existir caso os papéis dos dois elementos -- caminhos e conjuntos independentes -- fossem invertidos. A questão natural que surge é então se há relação entre partições em conjuntos independentes (coloração) e coleções de caminhos direcionados. Essa relação ficou conhecida como versão dual da Conjectura de Berge. Dizemos que uma coloração $C$ e uma coleção de $k$ caminhos $P$, para um $k$ inteiro positivo, são \emph{ortogonais} se cada classe de cor de $C$ intersecta o maior número de caminhos possíveis em $P$, isto é, a intersecção é a classe toda se esta tem cardinalidade menos que $k$ ou $k$ caso contrário. Tal conjectura é falsa para digrafos em geral e apresenta contraexemplo. Entretanto, os contraexemplos conhecidos possuem ciclo ímpar e não há registro na literatura de ter sido pesquisado se a conjectura seria válida para dígrafos sem ciclos ímpares, isto é, digrafos bipartidos. Desse modo, este projeto pretende estudar de maneira mais aprofundada a relação entre coloração e coleções de caminhos, e verificar se a Conjectura Dual de Berge é verdadeira para digrafos bipartidos.