Decomposition by maximal cliques and forbidden subgraphs for path graphs
Abstract
In this work, we study some aspects of characterizations by forbiddance. In the general case, we investigate the existence of these characterizations in quasiordered sets, when certain special properties are required. In the case of graphs, we design an algorithm for decomposition by maximal clique separators, which is applicable in the search for forbidden subgraphs for some classes of path graphs. Finally, we apply known techniques, as well as a tool which is introduced in this work, to find an infinite family of forbidden subgraphs for the class of path graphs UE.References
Cerioli, M. R. and Petito, P. (2005). Forbidden subgraph characterization of split graphs that are UEH. Electronic Notes in Discrete Mathematics, 19:305 – 311. Proceedings of GRACO 2005.
Lévêque, B., Maffray, F., and Preissmann, M. (2009). Characterizing path graphs by forbidden induced subgraphs. Journal of Graph Theory, 62:369 – 384.
Lovász, L. (2006). Graph minor theory. Bulletin (New Series) of the American Mathematical Society, 43(1):75 – 86.
Monma, C. L. and Wei, V. K. (1986). Intersection graphs of paths in a tree. Journal of Combinatorial Theory, Series B, 41(2):141 – 181.
Panda, B. S. (1999). The forbidden subgraph characterization of directed vertex graphs. Discrete Mathematics, 196(1):239 – 256.
Petito, P. C. (2002). Grafos de interseção em arestas de caminhos em uma Árvore. Master’s thesis, Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro.
Spinrad, J. P. (2003). Efficient Graph Representations. American Mathematical Society, Providence, RI, EUA.
Tarjan, R. E. (1985). Decomposition by clique separators. Discrete Mathematics, 55(2):221 – 232.
Tondato, S. B., Gutierrez, M., and Szwarcfiter, J. L. (2005). A forbidden subgraph characterization of path graphs. Electronic Notes in Discrete Mathematics, 19:281 – 287. Proceedings of GRACO 2005.
Lévêque, B., Maffray, F., and Preissmann, M. (2009). Characterizing path graphs by forbidden induced subgraphs. Journal of Graph Theory, 62:369 – 384.
Lovász, L. (2006). Graph minor theory. Bulletin (New Series) of the American Mathematical Society, 43(1):75 – 86.
Monma, C. L. and Wei, V. K. (1986). Intersection graphs of paths in a tree. Journal of Combinatorial Theory, Series B, 41(2):141 – 181.
Panda, B. S. (1999). The forbidden subgraph characterization of directed vertex graphs. Discrete Mathematics, 196(1):239 – 256.
Petito, P. C. (2002). Grafos de interseção em arestas de caminhos em uma Árvore. Master’s thesis, Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro.
Spinrad, J. P. (2003). Efficient Graph Representations. American Mathematical Society, Providence, RI, EUA.
Tarjan, R. E. (1985). Decomposition by clique separators. Discrete Mathematics, 55(2):221 – 232.
Tondato, S. B., Gutierrez, M., and Szwarcfiter, J. L. (2005). A forbidden subgraph characterization of path graphs. Electronic Notes in Discrete Mathematics, 19:281 – 287. Proceedings of GRACO 2005.
Published
2012-07-16
How to Cite
NOBREGA, Hugo de H. C.; CERIOLI, Márcia R.; VIANA, Jorge Petrúcio.
Decomposition by maximal cliques and forbidden subgraphs for path graphs. In: THESIS AND DISSERTATION CONTEST (CTD), 15. , 2012, Curitiba/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2012
.
p. 43-48.
ISSN 2763-8820.
