Dissertação de Mestrado

The decomposition of a connected graph by the set of its cut-vertices, sometimes called the "block decomposition" or "block tree" of a graph, is a well known and basic concept in graph theory. This decomposition, however, does not provide meaningful information when applied to a k-connected graph for k > 1. There has been a number of attempts to generalize the construction of the block decomposition of a graph for the case of k-connected graphs. Notably, Tutte constructed a tree that describes the mutual arrangement of 2-cutsets in a 2-connected graph. This decomposition has some similarities to the block decomposition of a connected graph. In other works, a block of a k-connected graph was defined as a maximal (k+1)-connected subgraph. Karpov described the decomposition of a k-connected graph by the set of k-cutsets that are not separated by any other k-cutset of the graph. Karpov also described some special properties of his decomposition for the case of a 2-connected graph. The decompositions defined by Karpov and Tutte for the case of a 2-connected graph share some similarities. In this work, we present a self-contained description of Karpov's decomposition. We also present some applications to the study of planarity, the chromatic number, critically 2-connected graphs, and the partition of certain 2-connected graphs into three connected subgraphs.

A decomposição de um grafo conexo pelo conjunto de seus vértices de corte, às vezes chamada de "decomposição por blocos" ou "árvore de blocos" de um grafo, é um conceito bem conhecido e básico na teoria dos grafos. Essa decomposição, no entanto, não fornece informações significativas quando é aplicada a um grafo k-conexo para k >1. Tem havido uma série de tentativas de generalizar a construção da decomposição em blocos para grafos k-conexos. Notavelmente, Tutte construiu uma árvore que descreve o arranjo mútuo dos 2-cutsets em um grafo 2-conexo. Esta decomposição tem algumas semelhanças com a decomposição por blocos de um grafo conexo. Em outros trabalhos, um bloco de um grafo k-conexo é definido como um subgrafo (k+1)-conexo maximal. Karpov descreveu a decomposição de um grafo k-conexo pelo conjunto dos seus k-cutsets que não são separados por nenhum outro k-cutset do grafo. Karpov também descreveu algumas propriedades de sua decomposição para o caso de um grafo 2-conexo. As decomposições definidas por Karpov e Tutte para o caso de grafos 2-conexos compartilham algumas semelhanças. Neste trabalho, nós apresentamos uma descrição autocontida da decomposição de Karpov. Nós também apresentamos algumas aplicações para o estudo de planaridade, número cromático, grafos criticamente 2-conexos, e a partição de certos grafos 2-conexos em três subgrafos conexos.