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

DOI10.1016/S0012-365X(01)00268-0zbMath1004.05027MaRDI QIDQ1613431

Claudio Arbib, Raffaele Mosca

Publication date: 29 August 2002

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmscoloring problemstable set problemclique cover problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Related Items

On indicated chromatic number of graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Colouring diamond-free graphs ⋮ Powers of edge ideals with linear resolutions ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Coloring graphs without induced \(P_5\) or \(K_5-e\) ⋮ On indicated coloring of graphs ⋮ Colouring of \((P_3 \cup P_2)\)-free graphs ⋮ On easy and hard hereditary classes of graphs with respect to the independent set problem ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ \(P_{5}\)-free augmenting graphs and the maximum stable set problem ⋮ Some results on maximum stable sets in certain \(P_{5}\)-free graphs ⋮ First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ On the stable set problem in special \(P_{5}\)-free graphs