Tournament pathwidth and topological containment.

*(English)*Zbl 1301.05148Summary: 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.

##### MSC:

05C20 | Directed graphs (digraphs), tournaments |

PDF
BibTeX
XML
Cite

\textit{A. Fradkin} and \textit{P. Seymour}, J. Comb. Theory, Ser. B 103, No. 3, 374--384 (2013; Zbl 1301.05148)

Full Text:
DOI

##### References:

[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.