zbMATH — the first resource for mathematics

Tournament pathwidth and topological containment. (English) Zbl 1301.05148
Summary: We prove that if a tournament has pathwidth \(\geq 4\theta^2+7\theta\) then it has \(\theta\) vertices that are pairwise \(\theta\)-connected. As a consequence of this and previous results, we obtain that for every set \(S\) of tournaments the following are equivalent: (1) there exists \(k\) such that every member of \(S\) has pathwidth at most \(k\), (2) there is a digraph \(H\) such that no subdivision of \(H\) is a subdigraph of any member of \(S\), (3) there exists \(k\) such that for each \(T\in S\), there do not exist \(k\) vertices of \(T\) that are pairwise \(k\)-connected. As a further consequence, we obtain a polynomial-time algorithm to test whether a tournament contains a subdivision of a fixed digraph \( H\) as a subdigraph.

05C20 Directed graphs (digraphs), tournaments
Full Text: DOI
[1] M. Chudnovsky, A. Scott, P. Seymour, Disjoint paths in tournaments, submitted for publication. · Zbl 1304.05057
[2] Fomin, F.; Pilipczuk, M., Jungles, bundles, and fixed parameter tractability
[3] Fortune, S.; Hopcroft, J.; Wyllie, J., The directed subgraph homeomorphism problem, Theoret. Comput. Sci., 10, 111-121, (1980) · Zbl 0419.05028
[4] A. Fradkin, P. Seymour, Edge-disjoint paths in digraphs with bounded independence number, submitted for publication. · Zbl 1302.05067
[5] Ramsey, F. P., On a problem of formal logic, Proc. London Math. Soc., 30, 264-286, (1930) · JFM 55.0032.04
[6] Thomassen, C., Connectivity in tournaments, (Graph Theory and Combinatorics, (1984), Academic Press London) · Zbl 0546.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.