Corrigendum: To: D. Bienstock, “On the complexity of testing for odd holes and induced odd paths” Discrete Mathematics 90 (1991) 85–92.

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 35 KB
• Volume: 102
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90357-l

✦ Synopsis

Bruce Reed has pointed out a flaw in the construction which renders (2.1) false. Namely, a u-hole may contain, for some variable xi, a subpath of the form (for example) fi,4, c~,~,&,~,~&,$(x~), for some j, and thus subgraph CU~+~ is not visited in the expected way. This is corrected by adding to each subgraph LX~, the red edges {&, ti,3}, {b7f;,3h and {h r,l t. }. Refer to Fig. below.