Просмотр кода страницы P 4-Sparse graph

'''<math>P_{4}</math>-Sparse graph''' --- <math>P_{4}</math>-разреженный граф. 

The class of '''<math>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>P_{4}</math> (i.e., a path of length 4). This class contains the
class of <math>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>{\mathcal O}(|V| + |E|)</math> time algorithms are proposed for solving
five optimization problems on the class of <math>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>(q,t)</math> graphs which,
for <math>t = q-4</math>, extends the class of <math>P_{4}</math>-sparse graphs. In such a
graph no set of at most <math>q</math> vertices is allowed to induce more than
<math>t</math> distinct <math>P_{4}</math>'s. <math>(4,0)</math> graphs are exactly the ''cographs''.