Even and odd holes in cap-free graphs

✍ Scribed by Conforti, Michele; Cornu�jols, G�rard; Kapoor, Ajai; Vu?kovi?, Kristina

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 158 KB
• Volume: 30
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199904)30:4<289::aid-jgt4>3.0.co;2-3

✦ Synopsis

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β-perfect. In this article, we extend the problem of testing whether G(V, 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 odd (resp. even) number of odd edges. 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 called even-signable. Graphs that can be signed so that every triangle is odd and every hole is odd are called odd-signable. We derive from a theorem due to Truemper co-NP characterizations of even-signable and odd-