DOI

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.

Язык оригиналаанглийский
Страницы (с-по)232-243
Число страниц12
ЖурналJournal of Mathematical Sciences (United States)
Том204
Номер выпуска2
DOI
СостояниеОпубликовано - 2015

    Предметные области Scopus

  • Теория вероятности и статистика
  • Математика (все)
  • Прикладная математика

ID: 36925418