Partição de Grafos P_4-esparsos em 2 Florestas

Vol 53, 2021 - 139602
Prêmio de IC
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Nesse trabalho consideramos o problema dab arboricidade em grafos. Arboricidade e coloração são problemas intimamente relacionados. Em ambos, desejamos particionar os vértices do grafo em subconjuntos esparsos. No primeiro, em subconjuntos acíclicos (i.e., florestas), o segundo em conjuntos independentes. Determinar a arboricidade de um grafo é um problema NP-difícil para grafos gerais. Neste trabalho, desejamos verificar, sob quais condições, um grafo P4-esparso possui arboricidade 2. Grafos que admitem um particionamento dos seus vértices em 2 florestas serão chamados grafos-2F. Apresentamos uma caracterização por subgrafos minimais proibidos para a classe dos grafos P4-esparsos-2F. Para o caso da arboricidadep >2, generalizamos nossa família de subgrafos proibidos e observamos que cada grafo nessa família é uma obstrução mininal para arboricidade p. Como o número de obstruções minimais P4-esparsas para arboricidade p cresce exponencialmente, não é possível uma caracterização análoga àquela para arboricidade 2.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Departamento de Ciência da Computação/ UFF
  • 2 Universidade Federal Fluminense
Eixo Temático
  • 19 - TAG – Teoria e Algoritmos em Grafos
Palavras-chave
Grafos P_4-esparso
Grafos-2F
Arboricidade