Problema de partição em conjunto independente e árvore quando restrito à classe dos grafos-P4-tidy - Silva, Fábio; Bravo, Raquel; Oliveira, Rodolfo; Souza, Uéverton (Anais do Encontro de Teoria da Computação (ETC), 2018)
Consideramos neste trabalho o problema de particionar o conjunto de vértices de um grafo em um conjunto independente (sem arestas entre os vértices) e em umaárvore (grafo livre de ciclos e conexo) denominada (S, T)-partição. Apresentaremos uma caracterização por subgrafos proibidos minimais da (S, T)-partição dos grafos restritosá classe dos grafos P 4 -tidy. Como resultado adicional, disponibilizamos um algoritmo de reconhecimento desta partição em tempo linear para os grafos P 4 -tidy, utilizando a prova de caracterização dos subgrafos proibidos.