Even directed cycles in H-free digraphs
Anna Galluccio, Martin Loebl, Consiglio Nazionale delle Ricerche, Rome (Italy). Istituto di Analisi dei Sistemi ed Informatica · 1995
A digraph is H-free if its underlying graph does not contain a subgraph contractible to the graph H. We provide a polynomial-time algorithm to solve the Even Cycle Problem in the class of K3,3-free digraphs and in the class of K5-free digraphs. We also discuss the important role played by the subdivisions of K3,3 in solving the Even Cycle Problem in its generality.