Gregory Gutin, Sudakov, B. and Yeo, A. (1998) Note on alternating directed cycles. Discrete Mathematics, 191
Full text access: Open
The problem of the existence of an alternating simple dicycle in a 2-arc-coloured digraph is considered. This is a generalization of the alternating cycle problem in 2-edge-coloured graphs and the even dicycle problem (both are polynomial time solvable). We prove that the alternating dicycle problem is -complete. Let ƒ(n) (g(n), resp.) be the minimum integer such that if every monochromatic indegree and outdegree in a strongly connected 2-arc-coloured digraph (any 2-arc-coloured digraph, resp.) D is at least f(n) (g(n), resp.), then D has an alternating simple dicycle. We show that ƒ(n) = Θ(log n) and g(n) = Θ(log n).
This is a Published version This version's date is: 1998 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/9770cbe1-013d-3a41-529a-ba113c72a8e5/1/
Deposited by () on 23-Dec-2009 in Royal Holloway Research Online.Last modified on 25-May-2010