Para citar este trabalho use um dos padrões abaixo:
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.
Com ~200 mil publicações revisadas por pesquisadores do mundo todo, o Galoá impulsiona cientistas na descoberta de pesquisas de ponta por meio de nossa plataforma indexada.
Confira nossos produtos e como podemos ajudá-lo a dar mais alcance para sua pesquisa:
Esse proceedings é identificado por um DOI , para usar em citações ou referências bibliográficas. Atenção: este não é um DOI para o jornal e, como tal, não pode ser usado em Lattes para identificar um trabalho específico.
Verifique o link "Como citar" na página do trabalho, para ver como citar corretamente o artigo