Abstrakt
As usual, P_n (n >= 1) denotes the path on n vertices, and C_n (n >= 3) denotes the cycle on n vertices. For a family H of graphs, we say that a graph G is H-free if no induced subgraph of G is isomorphic to any graph in H.
We present a decomposition theorem for the class of (P_7, C_4, C_5)-free graphs; in fact, we give a complete structural characterization of (P_7, C_4, C_5)-free graphs that do not admit a cliquecutset. We use this decomposition theorem to show that the class of (P_7, C_4, C_5)-free graphs is chi-bounded by a linear function (more precisely, every (P_7, C_4, C_5)-free graph G satisfies chi(G) = 3/2 omega(G)).
We also use the decomposition theorem to construct an O(n(3)) algorithm for the minimum coloring problem, an O(n(2)m) algorithm for the maximum weight stable set problem, and an O(n(3)) algorithm for the maximum