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.

Original languageEnglish
Pages (from-to)232-243
Number of pages12
JournalJournal of Mathematical Sciences (United States)
Volume204
Issue number2
DOIs
StatePublished - 2015

    Research areas

  • Chromatic number, Terminal Part, Decomposition Tree, Boundary Vertex, Decomposition Part

    Scopus subject areas

  • Statistics and Probability
  • Mathematics(all)
  • Applied Mathematics

ID: 36925418