Independent set and tree partition problem when restricted to the class of P4-tidy graphs
Abstract
We consider in this work the problem of partitioning the vertex set of a graph into an independent set (a graph without edges between its vertices) and into a tree (a connected graph that has no cycles) called (S,T)-partition. We will present a characterization by minimal forbidden subgraphs of (S,T)-partition of the P4-tidy graphs. As an additional result, we have provided an algorithm of recognizing this partition in linear time for P4-tidy graphs, using the proof of the characterization by forbidden subgraphs.
References
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.
Published
2018-07-26
How to Cite
SILVA, Fábio; BRAVO, Raquel; OLIVEIRA, Rodolfo; SOUZA, Uéverton.
Independent set and tree partition problem when restricted to the class of P4-tidy graphs. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
