On (\(P_{5}\), diamond)-free graphs (Q1613431)

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.