Directed path-width and monotonicity in digraph searching

Janos Barat

    Research output: Contribution to journalJournal articleResearchpeer-review


    Directed path-width was defined by Reed, Thomas and Seymour around 1995. The author and P. Hajnal defined a cops-and-robber game on digraphs in 2000. We prove that the two notions are closely related and for any digraph D, the corresponding graph parameters differ by at most one. The result is achieved using the mixed-search technique developed by Bienstock and Seymour. A search is called monotone, in which the robber's territory never increases. We show that there is a mixed-search of D with k cops if and only if there is a monotone mixed-search with k cops. For our cops-and-robber game we get a slightly weaker result: the monotonicity can be guaranteed by using at most one extra cop.
    Original languageEnglish
    JournalGraphs and Combinatorics
    Issue number2
    Pages (from-to)161-172
    Publication statusPublished - Jun 2006


    • search games
    • path-width
    • cops-and-robber games
    • monotonicity
    • directed graph


    Dive into the research topics of 'Directed path-width and monotonicity in digraph searching'. Together they form a unique fingerprint.

    Cite this