The class of (P7,C4,C5)‐free graphs: Decomposition, algorithms, and χ‐boundedness.

As usual, Pn (n≥1) denotes the path on n vertices, and Cn (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 (P7,C4,C5)‐free graphs; in fact, we give a complete structural characterization of (P7,C4,C5)‐free graphs that do not admit a clique‐cutset. We use this decomposition theorem to show that the class of (P7,C4,C5)‐free graphs is χ‐bounded by a linear function (more precisely, every (P7,C4,C5)‐free graph G satisfies χ(G)≤3/2ω(G)). We also use the decomposition theorem to construct an O(n3) algorithm for the minimum coloring problem, an O(n2m) algorithm for the maximum weight stable set problem, and an O(n3) algorithm for the maximum weight clique problem for this class, where n denotes the number of vertices and m the number of edges of the input graph. [ABSTRACT FROM AUTHOR]