On (\(P_{5}\), diamond)-free graphs (Q1613431)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On (\(P_{5}\), diamond)-free graphs |
scientific article |
Statements
On (\(P_{5}\), diamond)-free graphs (English)
0 references
29 August 2002
0 references
The authors study the stable set problem (SSP), the coloring problem (CP) and the clique cover problem (CCP) of graphs with no induced path on 5 vertices \((P_5)\) and no induced diamond \((K_4-e)\). They give polynomial algorithms for solving CP and CCP on such graphs. As for SSP they improve previus \(O(n^4)\) time bound to \(O(n^2)\) for these graphs. They also show the possibility of desribing imperfect (\(P_5\), diamond)-free graphs via elementary graph operations such as vertex multiplication or substitution from a limited set of small basic graphs. Corollaries of this result and other structural properties are a complete description of the stable set polytope for imperfect (\(P_5\), diamond)-free graphs and the existence of a non-trivial subclass of these graphs whose elements are \(h\)-perfect but generally not \(t\)-perfect.
0 references
stable set problem
0 references
coloring problem
0 references
clique cover problem
0 references
polynomial algorithms
0 references