Problema de partição em conjunto independente e árvore quando restrito à classe dos grafos-P4-tidy
Resumo
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 P4-tidy. Como resultado adicional, disponibilizamos um algoritmo de reconhecimento desta partição em tempo linear para os grafos P4-tidy, utilizando a prova de caracterização dos subgrafos proibidos.
Referências
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2017). Independent feedback vertex set for p 5-free graphs. arXiv preprint arXiv:1707.09402.
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131:26–32.
Brandstädt, A., Brito, S., Klein, S., Nogueira, L. T., and Protti, F. (2013). Cycle transversals in perfect graphs and cographs. Theoretical Computer Science, 469:15–23.
Dross, F., Montassier, M., and Pinlou, A. (2016). Partitioning sparse graphs into an independent set and a forest of bounded degree. arXiv preprint arXiv:1606.04394.
Giakoumakis, V., Roussel, F., and Thuillier, H. (1997). On p4-tidy graphs. Discrete Mathematics and Theoretical Computer Science, 1.
Golumbic, M. C. (2004). Algorithmic graph theory and perfect graphs, volume 57. Elsevier.
Roussel, F., Rusu, I., and Thuillier, H. (1999). On graphs with limited number of p4-partners. International Journal of Foundations of Computer Science, 10(01):103–121.
Saaty, T. (1977). The four-color problem : assaults and conquest. McGraw-Hill International Book Co, New York.
Yang, A. and Yuan, J. (2006). Partition the vertices of a graph into one independent set and one acyclic set. Discrete mathematics, 306(12):1207–1216.
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131:26–32.
Brandstädt, A., Brito, S., Klein, S., Nogueira, L. T., and Protti, F. (2013). Cycle transversals in perfect graphs and cographs. Theoretical Computer Science, 469:15–23.
Dross, F., Montassier, M., and Pinlou, A. (2016). Partitioning sparse graphs into an independent set and a forest of bounded degree. arXiv preprint arXiv:1606.04394.
Giakoumakis, V., Roussel, F., and Thuillier, H. (1997). On p4-tidy graphs. Discrete Mathematics and Theoretical Computer Science, 1.
Golumbic, M. C. (2004). Algorithmic graph theory and perfect graphs, volume 57. Elsevier.
Roussel, F., Rusu, I., and Thuillier, H. (1999). On graphs with limited number of p4-partners. International Journal of Foundations of Computer Science, 10(01):103–121.
Saaty, T. (1977). The four-color problem : assaults and conquest. McGraw-Hill International Book Co, New York.
Yang, A. and Yuan, J. (2006). Partition the vertices of a graph into one independent set and one acyclic set. Discrete mathematics, 306(12):1207–1216.
Publicado
26/07/2018
Como Citar
SILVA, Fábio; BRAVO, Raquel; OLIVEIRA, Rodolfo; SOUZA, Uéverton.
Problema de partição em conjunto independente e árvore quando restrito à classe dos grafos-P4-tidy. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 21-24.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3142.
