Even cycles in directed graphs (Q1084409): Difference between revisions

In this article the author shows that given an edge e in a digraph G it is NP-complete to decide if D has an odd cycle through e and it is NP- complete to decide if D has an even cycle through e. Contiuing his investigation of even cycles in digraphs, he shows that for every natural number k, there exists a digraph \(D_ k\) with no even cycle such that every vertex of \(D_ k\) has outdegree k (settling problems of Lovasz and Seymour). Furthermore, he proves that a digraph of order n and minimum outdegree \([\log_ 2n]+1\) contains, for each edge set E, a cycle containing an even number of edges of E, and this bound is best possible.