Research output: Contribution to journal › Article › peer-review
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 language | English |
---|---|
Pages (from-to) | 232-243 |
Number of pages | 12 |
Journal | Journal of Mathematical Sciences (United States) |
Volume | 204 |
Issue number | 2 |
DOIs | |
State | Published - 2015 |
ID: 36925418