Structure and algorithms for (cap,even hole)-free graphs

A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph $G$ has a vertex of degree at most $\frac{3}{2}\omega \left(G\right)?1$, and hence $\chi \left(G\right)\le \frac{3}{2}\omega \left(G\right)$, where $\omega \left(G\right)$ denotes the size of a largest clique in $G$ and $\chi \left(G\right)$ denotes the chromatic number of $G$. We give an $O\left(nm\right)$ algorithm for $q$-coloring these graphs for fixed $q$ and an $O\left(nm\right)$ algorithm for maximum weight stable set, where $n$ is the number of vertices and $m$ is the number of edges of the input graph. We also give a polynomial-time algorithm for minimum coloring.Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs $G$ without clique cutsets have treewidth at most $6\omega \left(G\right)?1$ and clique-width at most 48.