As usual, $P_n$ ($n geq 1$) denotes the path on $n$ vertices, and $C_n$ ($n geq 3$) denotes the cycle on $n$ vertices. For a family $mathcal{H}$ of graphs, we say that a graph $G$ is $mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to any graph in $mathcal{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 clique-cutset. 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) leq frac{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^2m)$ algorithm for the maximum weight stable set problem, and an $O(n^3)$ 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.
تحميل البحث