TY - JOUR

T1 - The Decomposition Tree of a Biconnected Graph

AU - Karpov, D. V.

N1 - Karpov, D.V. The Decomposition Tree of a Biconnected Graph. J Math Sci 204, 232–243 (2015). https://doi.org/10.1007/s10958-014-2198-z

PY - 2015

Y1 - 2015

N2 - The decomposition tree of a biconnected graph is in brief the decomposition tree of a biconnected graph by the set of all single cutsets of it (i.e., 2-vertex cutsets that are independent with all other 2-vertex cutsets). It is shown that this tree has much in common with the classical tree of blocks and cutpoints of a connected graph. With the help of the decomposition tree of a biconnected graph, a planarity criterion is proved and some upper bounds on the chromatic number of this graph are found. Finally, the structure of critical biconnected graphs is studied, and it is proved that each such graph has at least four vertices of degree 2. Bibliography: 11 titles.

AB - The decomposition tree of a biconnected graph is in brief the decomposition tree of a biconnected graph by the set of all single cutsets of it (i.e., 2-vertex cutsets that are independent with all other 2-vertex cutsets). It is shown that this tree has much in common with the classical tree of blocks and cutpoints of a connected graph. With the help of the decomposition tree of a biconnected graph, a planarity criterion is proved and some upper bounds on the chromatic number of this graph are found. Finally, the structure of critical biconnected graphs is studied, and it is proved that each such graph has at least four vertices of degree 2. Bibliography: 11 titles.

KW - Chromatic number

KW - Terminal Part

KW - Decomposition Tree

KW - Boundary Vertex

KW - Decomposition Part

UR - http://www.scopus.com/inward/record.url?scp=84925487835&partnerID=8YFLogxK

U2 - 10.1007/s10958-014-2198-z

DO - 10.1007/s10958-014-2198-z

M3 - Article

AN - SCOPUS:84925487835

VL - 204

SP - 232

EP - 243

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 2

ER -