Even and odd holes in cap-free graphs

It is an old problem in graph theory to test whether a graph contains a cho rdless cycle of length greater than three (hole) with a specific parity (ev en, odd). Studying the structure of graphs without odd holes has obvious im plications for Berge's strong perfect graph conjecture that states that a g raph G is perfect if and only if neither G nor its complement contain an od d hole. Markossian, Gasparian, and Reed have proven that if neither G nor i ts complement contain an even hole, then G is P-perfect. In this article, w e extend the problem of testing whether G(Si, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an add (resp, even) number of odd e dges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are c alled even-signable. Graphs that can be signed so that every triangle is od d and every hole is odd are called odd-signable. We derive from a theorem d ue to Truemper co-NP characterizations of even-signable and odd-signable gr aphs. A graph is strongly even-signable if it can be signed so that every c ycle of length greater than or equal to 4 with at most one chord is even an d every triangle is odd. Clearly a strongly even-signable graph is even-sig nable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd-signable. Every strongly odd-signable graph is odd-sig nable. We give co-NP characterizations for both strongly even-signable and strongly odd-signable graphs. A cnp is a hole together with a node, which i s adjacent to exactly two adjacent nodes on the hole. We derive a decomposi tion theorem for graphs that contain no cap as induced subgraph (cap-free g raphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well-studied subclass of cap-free graphs. If a graph is strongly even-signable or strongly odd-signable, then it is cap -free. In fact, strongly even-signable graphs are those cap-free graphs tha t are even-signable. From our decomposition theorem, we derive decompositio n results for strongly odd-signable and strongly even-signable graphs. Thes e results lead to polynomial recognition algorithms for testing whether a g raph belongs to one of these classes. (C) 1999 John Wiley & Sons, Inc. J