A generalization of the block decomposition for k-connected graphs

• Jared León USP

DOI: https://doi.org/10.5753/etc.2022.223106

Abstract

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 any meaningful information when applied to a $k$-connected graph for $k \geq 2$. 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. In this work, we present an outline of one such attempt by Karpov. We also present some applications of this decomposition to the study of planarity, the chromatic number, and critically $2$-connected graphs.

Keywords: block decomposition, block tree, $k$-connectivity

References

Hamidoune, Y. O. (1980). On critically h-connected simple graphs. Discrete Math., 32(3):257–262.

Karpov, D. V. (2013). The decomposition tree of a two-connected graph. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 417(VI):86–105.

Mac Lane, S. (1937). A structural characterization of planar combinatorial graphs. Duke Math. J., 3(3):460–472.

Tutte, W. T. (1966). Connectivity in graphs. Mathematical Expositions, No. 15. University of Toronto Press, Toronto, Ont.; Oxford University Press, London.