We study the stability number, chromatic number and clique cover of graphs with no induced P5 and diamonds. In particular, we provide a way to obtain all imperfect (P5, diamond)-free graphs by iterated point multiplication or substitution from a finite collection of small basic graphs. Corollaries of this and other structural properties, among which a result of Bacso and Tuza, are (i) combinatorial algorithms to solve coloring, clique cover and stable set in the class of (P5, diamond)-free graphs, (ii) a complete description of the stable set polytope of (P5, diamond)-free graphs, and (iii) the existence of non-trivial h-perfect graphs which are not t-perfect.
On (P5, diamond)-free Graphs
ARBIB, CLAUDIO;
2002-01-01
Abstract
We study the stability number, chromatic number and clique cover of graphs with no induced P5 and diamonds. In particular, we provide a way to obtain all imperfect (P5, diamond)-free graphs by iterated point multiplication or substitution from a finite collection of small basic graphs. Corollaries of this and other structural properties, among which a result of Bacso and Tuza, are (i) combinatorial algorithms to solve coloring, clique cover and stable set in the class of (P5, diamond)-free graphs, (ii) a complete description of the stable set polytope of (P5, diamond)-free graphs, and (iii) the existence of non-trivial h-perfect graphs which are not t-perfect.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
