On the \(p\)-connectedness of graphs---a survey (Q1302141)

A graph \(G\) is called \(p\)-connected if every partition \(V(G)= V_1\cup V_2\) is crossed by some \(P_4\in{\mathfrak P}_4(G)\), the set of induced 4-vertex paths in \(G\). Every graph decomposes into maximal \(p\)-connected induced subgraphs, the \(p\)-components. An important role play separable \(p\)-connected graphs which by definition allow a (then unique) decomposition \(V(G)= V_1\cup V_2\), where all \(V_1\), \(V_2\) crossing elements of \({\mathfrak P}_4(G)\) have exactly their end vertices in \(V_2\). The authors first recall a basic structure theorem for arbitrary graphs and its relation to the ``primeval'' decomposition into homogeneous sets. In sections 4 and 5 the analogy between \(p\)-connectedness and connectivity is stressed: \(p\)-chains, \(p\)-connected vertex pairs and \(p\)-articulations are addressed. In sections 6 and 7 reconstruction and decomposition of \(p\)-connected graphs are discussed. The considerations involve homogeneous and separable-homogeneous subsets of \(V(G)\) and lead (in section 8) to a refinement of the primeval decomposition. These refinements are related to certain graph operations and so-called \(p\)-trees. In section 9 on \(p\)-trees and \(p\)-forests are presented: various characterizations of \(p\)-trees and general classes of \(p\)-forests are described: for example cographs and \(P_4\)-reducible graphs are \(p\)-forests. Section 10 is devoted to graphs \(G\) with small \(|{\mathfrak P}_4(G)|\). The last section addresses algorithmic aspects, especially linear-time algorithms for the recognition and the computation of graph parameters of certain graph classes. Additional reference: \textit{A. Brandstädt}, \textit{Van Bang Le} and \textit{J. P. Spinrad} [Graph classes: a survey (SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA) (1999; Zbl 0919.05001)].