Vol 236, No 5 (2019)

Let n₁+n₂+n₃ = n, and let G be a 2-connected graph on n vertices such that any 2-vertex cutset of G splits it into at most three parts. We prove that there exists a decomposition of the vertex set of G into three disjoint subsets V₁, V₂, V₃ such that |V_i| = n_i and the induced subgraph G(V_i) is connected for every i.

We enumerate maximal chord diagrams up to all isomorphisms. The enumeration formula is based on a bijection between the rooted one-vertex one-face maps on locally orientable surfaces and a certain class of symmetric chord diagrams. This result extends the result of Cori and Marcus on the enumeration of maximal chord diagrams up to rotations.

A 3-connected graph G is said to be critical if for any vertex υ ∈ V (G) the graph G − υ is not 3-connected. Entringer and Slater proved that any critical 3-connected graph contains at least two vertices of degree 3. In this paper, a classification of critical 3-connected graphs with two vertices of degree 3 is given in the case where these vertices are adjacent. The case of nonadjacent vertices of degree 3 will be studied in the second part of the paper, which will be published later.

In this paper, we obtain a lower bound on the number of edges in a unit distance graph Γ in an infinitesimal plane layer ℝ² × [0, ε]^d, which relates the number of edges e(Γ), the number of vertices ν(Γ), and the independence number α(Γ). Our bound \( e\left(\varGamma \right)\ge \frac{19\nu \left(\varGamma \right)-50\alpha \left(\varGamma \right)}{3} \) is a generalization of a previous bound for distance graphs in the plane and a strong improvement of Turán’s bound in the case where \( \frac{1}{5}\le \frac{\alpha \left(\varGamma \right)}{v\left(\varGamma \right)}\le \frac{2}{7} \).