P4-Connected graph

[math]\displaystyle{ P_4 }[/math]-Connected graph --- [math]\displaystyle{ P_{4} }[/math]-связный граф.

A graph [math]\displaystyle{ G = (V,E) }[/math] is [math]\displaystyle{ P_{4} }[/math]-connected graph if for every partition of [math]\displaystyle{ V }[/math] into nonempty disjoint sets [math]\displaystyle{ V_{1} }[/math] and [math]\displaystyle{ V_{2} }[/math], some chordless path on four vertices and three edges (i.e. [math]\displaystyle{ P_{4} }[/math]) contains vertices from both [math]\displaystyle{ V_{1} }[/math] and [math]\displaystyle{ V_{2} }[/math].

The concept of [math]\displaystyle{ P_{4} }[/math]-connectedness leads to a structure theorem for arbitrary graphs in terms of [math]\displaystyle{ P_{4} }[/math]-connected components and suggests, in a quite natural way, a tree representation unique up to isomorphism. The leaves of the resulting tree are [math]\displaystyle{ P_{4} }[/math]-connected components and weak vertices, that is, vertices belonging to no [math]\displaystyle{ P_{4} }[/math]-connected component. The structure theorem and the corresponding tree repre\-sen\-ta\-tion provide tools for the study of graphs with a simple [math]\displaystyle{ P_{4} }[/math]-structure, such as [math]\displaystyle{ P_{4} }[/math]-reducible, [math]\displaystyle{ P_{4} }[/math]-extendible, [math]\displaystyle{ P_{4} }[/math]-sparse graphs.