P 4-Sparse graph

[math]\displaystyle{ P_{4} }[/math]-Sparse graph --- [math]\displaystyle{ P_{4} }[/math]-разреженный граф.

The class of [math]\displaystyle{ P_{4} }[/math]sparse graphs was introduced by Hoang (1985), as the class of graphs for which every set of five vertices induces at most one [math]\displaystyle{ P_{4} }[/math] (i.e., a path of length 4). This class contains the class of [math]\displaystyle{ P_{4} }[/math]-reducible graphs. These two classes contain the class of cographs. They have practical applications in the areas such as scheduling, clustering and computational semantics. It is known that linear [math]\displaystyle{ {\mathcal O}(|V| + |E|) }[/math] time algorithms are proposed for solving five optimization problems on the class of [math]\displaystyle{ P_{4} }[/math]-sparse graphs: maximum size clique, maximum size stable set, minimum coloring, minimum covering by cliques, and minimum fill-in.

Babel and Olariu (1995) introduced the class of [math]\displaystyle{ (q,t) }[/math] graphs which, for [math]\displaystyle{ t = q-4 }[/math], extends the class of [math]\displaystyle{ P_{4} }[/math]-sparse graphs. In such a graph no set of at most [math]\displaystyle{ q }[/math] vertices is allowed to induce more than [math]\displaystyle{ t }[/math] distinct [math]\displaystyle{ P_{4} }[/math]'s. [math]\displaystyle{ (4,0) }[/math] graphs are exactly the cographs.