Decomposition by maximal cliques and forbidden subgraphs for path graphs

• Hugo de H. C. Nobrega UFRJ
• Márcia R. Cerioli UFRJ
• Jorge Petrúcio Viana UFF

Resumo

Neste trabalho, estudamos alguns aspectos das caracterizações por proibição. No caso geral, investigamos a existência destas caracterizações em conjuntos quasiordenados, quando certas propriedades especiais são exigidas. No caso de grafos, nós elaboramos um algoritmo para decomposição por cliques maximais separadoras, que se aplica na busca de subgrafos proibidos para algumas classes de grafos de caminho. Finalmente, aplicamos técnicas já conhecidas, em conjunto com uma nova ferramenta introduzida neste trabalho, para encontrar uma família infinita de subgrafos proibidos para a classe de grafos de caminho UE.

Referências

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.