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

Vol 53, 2021 - 139602
Prêmio de IC
Favorite this paper
How to cite this paper?
Abstract

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.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Departamento de Ciência da Computação/ UFF
  • 2 Universidade Federal Fluminense
Track
  • 19 - TAG - Theory and Algorithms in Graphs
Keywords
Grafos P_4-esparso
Grafos-2F
Arboricidade