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 algorithms; coloring problem; stable set problem; clique cover problem

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C17: Perfect graphs

Related Items

Powers of edge ideals with linear resolutions, New applications of clique separator decomposition for the maximum weight stable set problem, On indicated coloring of graphs, First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs, Maximum independent sets in subclasses of \(P_{5}\)-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, Colouring of \((P_3 \cup P_2)\)-free graphs, Independent sets in extensions of 2\(K_{2}\)-free graphs, On the stable set problem in special \(P_{5}\)-free graphs, On indicated chromatic number of graphs, Colouring diamond-free graphs, Independent sets in some classes of \(S_{i,j,k}\)-free graphs, Independent Sets in Classes Related to Chair-Free Graphs