zbMATH — the first resource for mathematics

Tournaments and semicomplete digraphs. (English) Zbl 1407.05102
Bang-Jensen, Jørgen (ed.) et al., Classes of directed graphs. Cham: Springer. Springer Monogr. Math., 35-124 (2018).
Summary: The class of tournaments is by far the most well-studied class of digraphs with many deep and important results. Since J. W. Moon’s pioneering book [Topics on tournaments. New York etc: Holt, Rinehart and Winston (1968; Zbl 0191.22701)], the study of tournaments and their properties has flourished and research on tournaments is still a very active area. Often this research deals with the superclass of semicomplete digraphs which are digraphs with no pair of non-adjacent vertices (that is, contrary to tournaments, we allow directed cycles of length 2). In this chapter we cover a very broad range of results on tournaments and semicomplete digraphs from classical to very recent ones. In order to stimulate further research, we not only list a number of open problems, but also give a number of proofs which illustrate the diversity of proof techniques that have been applied. These range from elementary to quite advanced.
For the entire collection see [Zbl 1398.05002].

MSC:
 05C20 Directed graphs (digraphs), tournaments 05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
Full Text:
References:
 [1] L. Addario-Berry, F. Havet, C.L. Sales, B. Reed, and S. Thomassé. Oriented trees in digraphs. $$Discrete Math.$$, 313(8):967-974, 2013. · Zbl 1262.05066 [2] L. Addario-Berry, F. Havet, and S. Thomassé. Paths with two blocks in $$\(n$$\)-chromatic digraphs. $$J. Combin. Theory Ser. B$$, 97:620-626, 2007. · Zbl 1119.05049 [3] N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: ranking and clustering. In $$STOC 2005: 37th Annual ACM Symp. on Theory of Computing$$, pages 684-693. ACM Press, 2005. · Zbl 1192.90252 [4] N. Alon. Disjoint directed cycles. $$J. Combin. Theory Ser. B$$, 68(2):167-178, 1996. · Zbl 0861.05037 [5] N. Alon. Ranking tournaments. $$SIAM J. Discrete Math.$$, 20:137-142, 2006. · Zbl 1112.05043 [6] N. Alon, J. Bang-Jensen, and S. Bessy. Out-colourings of digraphs, manuscript 2017. [7] N. Alon, D. Lokshtanov, and S. Saurabh. Fast FAST. In $$ICALP 2009: 36th International Colloquium on Automata, Languages and Programming, Part I$$, volume 5555 of $$Lect. Notes Comput. Sci.$$, pages 49-58, 2009. [8] N. Alon and J.H. Spencer. $$The Probabilistic Method$$. John Wiley & Sons, New York, 1992. With an appendix by Paul Erdős. · Zbl 0767.05001 [9] N. Alon and J.H. Spencer. $$The Probabilistic Method$$. John Wiley & Sons, New York, 2nd edition, 2000. · Zbl 0996.05001 [10] N. Alon and J.H. Spencer. $$The Probabilistic Method$$. John Wiley & Sons, New York, 4th edition, 2016. · Zbl 1333.05001 [11] N. Alon, R. Yuster, and U. Zwick. Color-coding. $$J. Assoc. Comput. Mach.$$, 42:844-856, 1995. · Zbl 0885.68116 [12] B. Alspach. Cycles of each length in regular tournaments. $$Can. Math. Bull.$$, 10:283-285, 1967. · Zbl 0148.43602 [13] B. Alspach and M. Rosenfeld. Realization of certain generalized paths in tournaments. $$Discrete Math.$$, 34:199-202, 1981. · Zbl 0453.05031 [14] G. Araujo-Pardo and M. Olsen. A conjecture of Neumann-Lara on infinite families of r-dichromatic circulant tournaments. $$Discrete Math.$$, 310:489-492, 2010. · Zbl 1185.05071 [15] S. Arora, A. Frieze, and H. Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. $$Math. Program.$$, 92(1):1-36, 2002. · Zbl 1154.90602 [16] J. Bang-Jensen. Edge-disjoint in- and out-branchings in tournaments and related path problems. $$J. Combin. Theory Ser. B$$, 51(1):1-23, 1991. · Zbl 0659.05052 [17] J. Bang-Jensen. On the $$\(2$$\)-linkage problem for semicomplete digraphs. In $$Graph theory in memory of G. A. Dirac (Sandbjerg, 1985)$$, volume 41 of $$Ann. Discrete Math.$$, pages 23-37. North-Holland, 1989. [18] J. Bang-Jensen. Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs. $$Discrete Math.$$, 309:5655-5667, 2009. · Zbl 1207.05067 [19] J. Bang-Jensen, S. Bessy, and S. Thomassé. Disjoint 3-cycles in tournaments: a proof of the Bermond-Thomassen conjecture for tournaments. $$J. Graph Theory$$, 75:284-302, 2014. · Zbl 1292.05119 [20] J. Bang-Jensen and T.M. Christiansen. Degree constrained 2-partitions of semicomplete digraphs. manuscript. · Zbl 1401.05129 [21] J. Bang-Jensen, N. Cohen, and F. Havet. Finding good 2-partitions of digraphs II. Enumerable properties. $$Theor. Comput. Sci.$$, 640:1-19, 2016. · Zbl 1345.68168 [22] J. Bang-Jensen and G. Gutin. $$Digraphs: Theory, Algorithms and Applications$$. Springer-Verlag, London, 2nd edition, 2009. · Zbl 1170.05002 [23] J. Bang-Jensen and G. Gutin. Generalizations of tournaments: A survey. $$J. Graph Theory$$, 28:171-202, 1998. · Zbl 0920.05033 [24] J. Bang-Jensen and G. Gutin. Paths, trees and cycles in tournaments. $$Congr. Numer.$$, 115:131-170, 1996. Surveys in graph theory (San Francisco, 1995). · Zbl 0894.05032 [25] J. Bang-Jensen, G. Gutin, and A. Yeo. Hamiltonian cycles avoiding prescribed arcs in tournaments. $$Combin. Prob. Comput.$$, 6(3):255-261, 1997. · Zbl 0878.05036 [26] J. Bang-Jensen and F. Havet. Finding good 2-partitions of digraphs I. Hereditary properties. $$Theor. Comput. Sci.$$, 636:85-94, 2016. · Zbl 1342.68150 [27] J. Bang-Jensen and J. Huang. Quasi-transitive digraphs. $$J. Graph Theory$$, 20(2):141-161, 1995. · Zbl 0832.05048 [28] J. Bang-Jensen, J. Huang, and A. Yeo. Spanning $$\(k$$\)-arc-strong subdigraphs with few arcs in $$\(k$$\)-arc-strong tournaments. $$J. Graph Theory$$, 46(4):265-284, 2004. · Zbl 1057.05039 [29] J. Bang-Jensen and T. Jordán. Adding and reversing arcs in semicomplete digraphs. $$Combin. Prob. Comput.$$, 7(1):17-25, 1998. · Zbl 0892.05019 [30] J. Bang-Jensen and T. Jordán. Spanning 2-strong tournaments in 3-strong semicomplete digraphs. $$Discrete Math.$$, 310:1424-1428, 2010. · Zbl 1221.05172 [31] J. Bang-Jensen, A. Maddaloni, and S. Simonsen. Quasi-hamiltonian paths in semicomplete multipartite digraphs. $$Discrete Appl. Math.$$, 161:889-898, 2013. · Zbl 1262.05095 [32] J. Bang-Jensen, Y. Manoussakis, and C. Thomassen. A polynomial algorithm for Hamiltonian-connectedness in semicomplete digraphs. $$J. Algor.$$, 13(1):114-127, 1992. · Zbl 0749.68057 [33] J. Bang-Jensen and M.H. Nielsen. Finding complementary cycles in locally semicomplete digraphs. $$Discrete Appl. Math.$$, 146(3):245-256, 2005. · Zbl 1055.05086 [34] J. Bang-Jensen and C. Thomassen. A polynomial algorithm for the 2-path problem for semicomplete digraphs. $$SIAM J. Discrete Math.$$, 5:366-376, 1992. · Zbl 0759.05041 [35] J. Bang-Jensen and A. Yeo. Decomposing $$\(k$$\)-arc-strong tournaments into strong spanning subdigraphs. $$Combinatorica$$, 24(3):331-349, 2004. · Zbl 1064.05067 [36] J. Bang-Jensen and A. Yeo. Making a tournament $$\(k$$\)-arc-strong by reversing or deorienting arcs. $$Discrete Appl. Math.$$, 136(2-3):161-171, 2004. · Zbl 1035.05045 [37] F. Barbero, C. Paul, and M. Pilipczuk. Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs. In $$ICALP 2017: 44th International Colloquium on Automata, Languages, and Programming$$, volume 80 of $$LIPIcs$$, pages 70:1-70:13, 2017. [38] F. Barbero, C. Paul, and M. Pilipczuk. Strong immersion is a well-quasi-ordering for semicomplete digraphs. arXiv:1707.03563. [39] A. Benhocine and A.P. Wojda. On the existence of specified cycles in a tournament. $$J. Graph Theory$$, 7:469-473, 1983. · Zbl 0522.05027 [40] J. Bensmail, A. Harutyunyan, N.K. Le, B. Li, and N. Lichiardopol. Disjoint cycles of different lengths in graphs and digraphs. arXiv:1510.06667v2. · Zbl 1376.05038 [41] E. Berger, K. Choromanski, M. Chudnovsky, J. Fox, M. Loebl, A. Scott, P.D. Seymour, and S. Thomassé. Tournaments and colouring. $$J. Combin. Theory Ser. B$$, 103(1):1 - 20, 2013. · Zbl 1254.05064 [42] J.-C. Bermond and C. Thomassen. Cycles in digraphs—a survey. $$J. Graph Theory$$, 5(1):1-43, 1981. · Zbl 0458.05035 [43] S. Bessy, M. Bourgeret, and J. Thiebaut. Triangle packing in (sparse) tournaments: approximation and kernelization. arXiv:1707.04220. [44] A. Blass, G. Exoo, and F. Harary. Paley graphs satisfy all first-order adjacency axioms. $$J. Graph Theory$$, 5:435-439, 1981. · Zbl 0472.05058 [45] B. Bollobás and R. Häggkvist. Powers of Hamilton cycles in tournaments. $$J. Combin. Theory Ser. B$$, 50(2):309-318, 1990. · Zbl 0712.05030 [46] B. Bollobás and A. Thomason. Graphs which contain all small graphs. $$European J. Combin.$$, 2:13-15, 1981. · Zbl 0471.05037 [47] A. Bonato, P. Gordinowicz, and P. Pralat. Bounds and constructions for $$\(n$$\)-e.c. tournaments. $$Contributions to Discrete Math.$$, 5:52-66, 2010. · Zbl 1317.05160 [48] J.A. Bondy. Diconnected orientations and a conjecture of Las Vergnas. $$J. London Math. Soc. (2)$$, 14(2):277-282, 1976. · Zbl 0344.05124 [49] J.A. Bondy. Short proofs of classical theorems. $$J. Graph Theory$$, 44(3):159-165, 2003. · Zbl 1031.05046 [50] J.A. Bondy and U.S.R. Murty. $$Graph Theory$$, volume 244 of $$Graduate Texts in Mathematics.$$ Springer-Verlag, Berlin, 2008. [51] M. Bozóki. Nontransitive dice sets realizing the Paley tournaments for solving Schüte’s tournament problem. $$Miskolc Math. Notes$$, 15:39-50, 2014. · Zbl 1313.05150 [52] R.A. Brualdi and K. Kiernan. Landau’s and Rado’s Theorems and partial tournaments. $$Elec. J. Combin.$$, 16:# N2, 2009. · Zbl 1159.05014 [53] S.A. Burr. Subtrees of directed graphs and hypergraphs. $$Congress. Numer.$$, 28:227-239, 1980. [54] L. Caccetta and R. Häggkvist. On minimal digraphs with given girth. $$Congr. Numer.$$, 21:181-187, 1978. [55] M.-C. Cai, X. Deng, and W. Zang. An approximation algorithm for feedback vertex sets in tournaments. $$SIAM J. Comput.$$, 30(6):1993-2007, 2001. · Zbl 0980.68053 [56] P. Camion. Chemins et circuits hamiltoniens des graphes complets. $$C. R. Acad. Sci. Paris$$, 249:2151-2152, 1959. · Zbl 0092.15801 [57] S. Ceroi and F. Havet. Trees with three leaves are (n+1)-unavoidable. $$Discrete Appl. Math.$$, 141(13):19-39, 2004. Brazilian Symposium on Graphs, Algorithms and Combinatorics. · Zbl 1043.05057 [58] P. Charbit, S. Thomassé, and A. Yeo. The minimum feedback arc set problem is NP-hard for tournaments. $$Combin. Prob. Comput.$$, 16:1-4, 2007. · Zbl 1120.05038 [59] G. Chen, R.J. Gould, and H. Li. Partitioning Vertices of a Tournament into Independent Cycles. $$J. Combin. Theory Ser. B$$, 83:213-220, 2001. · Zbl 1028.05038 [60] G. Chen, J. Shen, and R. Yuster. Second neighborhood via first neighborhood in digraphs. $$Ann. Combin.$$, 7(1):15-20, 2003. · Zbl 1017.05057 [61] X. Chen, X. Hu, and W. Zang. A min-max theorem on tournaments. $$SIAM J. Comput.$$, 37(3):923-937, 2007. · Zbl 1191.90028 [62] M. Chudnovsky, A. Scott, and P.D. Seymour. Disjoint paths in tournaments. $$Adv. Math.$$, 270:582-597, 2015. · Zbl 1304.05057 [63] M. Chudnovsky, A. Scott, and P.D. Seymour. Disjoint paths in unions of tournaments. arXiv:1604.02317, 2016. · Zbl 1304.05057 [64] M. Chudnovsky and P.D. Seymour. A well-quasi-order for tournaments. $$J. Combin. Theory Ser. B$$, 101(1):47-53, 2011. · Zbl 1221.05178 [65] N. Cohen, F. Havet, W. Lochet, and N. Nisse. Subdivisions of oriented cycles in digraphs with large chromatic number. arXiv:1605.07762, May 2016. · Zbl 06997246 [66] Z. Cohn, A. Godbole, E. Wright Harkness, and Y. Zhang. The Number of Seymour Vertices in Random Tournaments and Digraphs. $$Graphs Combin.$$, pages 1-12, 2016. · Zbl 1351.05202 [67] A. Cuzzocrea, D. Taniar, S. Bessy, F. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh, and S. Thomassé. Kernels for feedback arc set in tournaments. $$J. Comput. Syst. Sci.$$, 77(6):1071-1078, 2011. · Zbl 1235.05134 [68] M. Darrah, Y.-P. Liu, and C.-Q. Zhang. Cycles of all lengths in arc-$$\(3$$\)-cyclic semicomplete digraphs. $$Discrete Math.$$, 173(1-3):23-33, 1997. · Zbl 0880.05056 [69] N. Dean and B.J. Latka. Squaring the tournament—an open problem. $$Congr. Numer.$$, 109:73-80, 1995. · Zbl 0904.05034 [70] W.F. de la Vega. On the maximum cardinality of a consistent set of arcs in a random tournament. $$J. Combin. Theory Ser. B$$, 35:328-332, 1983. · Zbl 0531.05036 [71] M. Dom, J. Guo, F. Hüffner, R. Niedermeier, and A. Truß. Fixed-parameter tractability results for feedback set problems in tournaments. In $$CIAC 2006: 6th Italian Conference on Algorithms and Complexity$$, pages 320-331, Berlin, Heidelberg, 2006. Springer-Verlag. · Zbl 1183.68419 [72] A. El Sahili. Paths with two blocks in $$\(k$$\)-chromatic digraphs. $$Discrete Math.$$, 287:151-153, 2004. · Zbl 1050.05072 [73] A. El Sahili. Trees in tournaments. $$J. Combin. Theory Ser. B$$, 92(1):183-187, 2004. · Zbl 1048.05040 [74] A. El Sahili and M. Kouider. About paths with two blocks. $$J. Graph Theory$$, 55:221-226, 2007. · Zbl 1121.05065 [75] P. Erdős. Graph theory and probability. $$Can. J. Math.$$, 11:34-38, 1959. · Zbl 0084.39602 [76] P. Erdős and L. Moser. On the representation of directed graphs as unions of orderings. $$Magyar Tud. Akad. Mat. Kutató Int. Közl.$$, 9:125-132, 1964. · Zbl 0136.44901 [77] G. Even, J. Naor, B. Schieber, and M. Sudan. Approximating minimum feedback sets and multicuts in directed graphs. $$Algorithmica$$, 20(2):151-174, 1998. · Zbl 0897.68078 [78] H. Fernau. A top-down approach to search-trees: Improved algorithmics for 3-hitting set. $$Algorithmica$$, 57(1):97-118, 2010. · Zbl 1184.68598 [79] D. Fidler and R. Yuster. Remarks on the second neighborhood problem. $$J. Graph Theory$$, 55(3):208-220, 2007. · Zbl 1122.05040 [80] D.C. Fisher. Squaring a tournament: a proof of Dean’s conjecture. $$J. Graph Theory$$, 23(1):43-48, 1996. · Zbl 0857.05042 [81] F.V. Fomin and M. Pilipczuk. Jungles, bundles and fixed-parameter tractability. In $$SODA 2013: 24th Annual ACM-SIAM Symposium on Discrete Algorithms$$, pages 396-413, 2013. [82] F.V. Fomin and M. Pilipczuk. Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph. In $$ESA 2013: 21st Annual European Symposium on Algorithms$$, pages 505-516, 2013. · Zbl 1395.68359 [83] R. Forcade. Parity of paths and circuits in tournaments. $$Discrete Math.$$, 6:115-118, 1973. · Zbl 0268.05108 [84] S. Fortune, J.E. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. $$Theor. Comput. Sci.$$, 10:111-121, 1980. · Zbl 0419.05028 [85] A. Fradkin and P.D. Seymour. Edge-disjoint paths in digraphs with bounded independence number. $$J. Combin. Theory Ser. B$$, 110:19-46, 2015. · Zbl 1302.05067 [86] A. Fradkin and P.D. Seymour. Tournament pathwidth and topological containment. $$J. Combin. Theory Ser. B$$, 103(3):374-384, 2013. · Zbl 1301.05148 [87] P. Fraisse and C. Thomassen. Hamiltonian dicycles avoiding prescribed arcs in tournaments. $$Graphs Combin.$$, 3(3):239-250, 1987. · Zbl 0622.05028 [88] A. Frank and T. Jordán. Directed vertex-connectivity augmentation. $$Math. Program. Ser. B$$, 84:537-553, 1999. · Zbl 0934.05081 [89] A. Frank and T. Jordán. Minimal edge-coverings of pairs of sets. $$J. Combin. Theory Ser. B$$, 65(1):73-110, 1995. · Zbl 0830.05051 [90] M.L. Fredman. On computing the length of longest increasing subsequences. $$Discrete Math.$$, 11(1):29-35, 1975. · Zbl 0312.68027 [91] A. Frieze and R. Kannan. Quick approximation to matrices and applications. $$Combinatorica$$, 19(2):175-220, 1999. · Zbl 0933.68061 [92] D. Gale, H. Kuhn, and A.W. Tucker. Linear programming and the theory of games. In $$Activity analysis of production and allocation$$, chapter XII. John Wiley and sons, New York, 1951. [93] H. Galeana-Sánchez and R. Rojas-Monroy. A counterexample to a conjecture on edge-coloured tournaments. $$Discrete Math.$$, 282(1-3):275-276, 2004. · Zbl 1042.05039 [94] T. Gallai. On directed paths and circuits. In $$Theory of Graphs (Proc. Colloq., Tihany, 1966)$$, pages 115-118. Academic Press, 1968. · Zbl 0159.54403 [95] S. Gaspers and M. Mnich. Feedback vertex sets in tournaments. $$J. Graph Theory$$, 72(1):72-89, 2013. · Zbl 1259.05070 [96] I.M. Gessel and R.P. Stanley. Algebraic enumeration. In $$Handbook of combinatorics, Vol. 1, 2$$, pages 1021-1061. Elsevier, Amsterdam, 1995. · Zbl 0853.05002 [97] J.R. Griggs and K.B. Reid. Landau’s theorem revisited. $$Australas. J. Combin.$$, 20:19-24, 1999. · Zbl 0946.05043 [98] B. Grünbaum. Antidirected Hamiltonian paths in tournaments. $$J. Combin. Theory Ser. B$$, 11:249-257, 1971. · Zbl 0198.29304 [99] Y. Guo. Spanning local tournaments in locally semicomplete digraphs. $$Discrete Appl. Math.$$, 79(1-3):119-125, 1997. · Zbl 0884.05047 [100] Q. Guo, Y. Li, S. Guo, and H. Li. Out-arc pancyclicity of vertices in tournaments. $$Discrete Appl. Math.$$, 158:996-1005, 2010. · Zbl 1220.05049 [101] Q. Guo, S. Li, H. Li, and H. Zhao. The number of vertices whose out-arcs are pancyclic in a strong tournament. $$Graphs Combin.$$, 30:1163-1173, 2014. · Zbl 1298.05144 [102] G. Gutin and R. Li. Seymour’s second neighbourhood conjecture for quasi-transitive oriented graphs. $$CoRR$$, abs/1704.01389, 2017. [103] R. Häggkvist. Hamilton cycles in oriented graphs. $$Combin. Prob. Comput.$$, 2(1):25-32, 1993. · Zbl 0795.05087 [104] R. Häggkvist and A.G. Thomason. Trees in tournaments. $$Combinatorica$$, 11(2):123-130, 1991. · Zbl 0736.05041 [105] M. Hasse. Zur algebraischen Begründung der Graphentheorie. I. $$Math. Nachr.$$, 28:275-290, 1964/1965. [106] F. Havet. On unavoidability of trees with $$\(k$$\) leaves. $$Graphs Combin.$$, 19(1):101-110, 2003. · Zbl 1022.05014 [107] F. Havet. Oriented Hamiltonian cycles in tournaments. $$J. Combin. Theory$$, 80:1-31, 2000. · Zbl 1026.05052 [108] F. Havet. Pancyclic arcs and connectivity in tournaments. $$J. Graph Theory$$, 47:87-110, 2004. · Zbl 1060.05037 [109] F. Havet and S. Thomassé. Median orders of tournaments: a tool for the second neighborhood problem and Sumner’s conjecture. $$J. Graph Theory$$, 35(4):244-256, 2000. · Zbl 0969.05029 [110] F. Havet and S. Thomassé. Oriented hamiltonian paths in tournaments: a proof of Rosenfeld’s conjecture. $$J. Combin. Theory Ser. B$$, 78:243-273, 2000. · Zbl 1026.05053 [111] F. Havet, S. Thomassé, and A. Yeo. Hoàng-Reed Conjecture holds for tournaments. $$Discrete Math.$$, 308:3412-3415, 2008. · Zbl 1147.05038 [112] C.T. Hoang and B. Reed. A note on short cycles in digraphs. $$Discrete Math.$$, 66(1-2):103-107, 1987. · Zbl 0626.05021 [113] B. Jackson. Long paths and cycles in oriented graphs. $$J. Graph Theory$$, 5(2):145-157, 1981. · Zbl 0458.05041 [114] T. Johnson, N. Robertson, P.D. Seymour, and R. Thomas. Directed Tree-Width. $$J. Combin. Theory Ser. B$$, 82(1):138-154, 2001. · Zbl 1027.05045 [115] T. Jordán. On the existence of $$\(k$$\) edge-disjoint 2-connected spanning subgraphs. $$J. Combin. Theory Ser. B$$, 95(2):257-262, 2005. · Zbl 1075.05050 [116] Y. Kaneko and S.C. Locke. The minimum degree approach for Paul Seymour’s distance 2 conjecture. $$Congress. Numer.$$, 148:201-206, 2001. · Zbl 0996.05042 [117] D.Y. Kang, J. Kim, Y. Kim, and G. Suh. Sparse spanning $$\(k$$\)-connected subgraphs in tournaments. arXiv:1603.02474. · Zbl 1371.05104 [118] R.M. Karp. Reducibility among combinatorial problems. In $$Complexity of computer computations (Proc. Symp., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972)$$, pages 85-103. Plenum, 1972. [119] P. Keevash, D. Kühn, and D. Osthus. An exact minimum degree condition for Hamilton cycles in oriented graphs. $$J. London Math. Soc.$$, 79:144-166, 2009. · Zbl 1198.05081 [120] I. Kim and P.D. Seymour. Tournament minors. $$J. Combin. Theory Ser. B$$, 112:138-153, 2015. · Zbl 1310.05109 [121] J. Kim, D. Kühn, and D. Osthus. Bipartitions of highly connected tournaments. $$SIAM J. Discrete Math.$$, 30:895-911, 2016. · Zbl 1336.05050 [122] R. Kim, S.-J. Kim, J. Ma, and B. Park. Cycles with two blocks in $$\(k$$\)-chromatic digraphs. $$CoRR$$, abs/1610.05839, October 2016. · Zbl 1393.05118 [123] S. Kreutzer and S. Tazari. Directed nowhere dense classes of graphs. In $$SODA 2012: 23rd Annual ACM-SIAM Symposium on Discrete Algorithms$$, pages 1552-1562, 2012. [124] D. Kühn, D. Lapinskas, J. Osthus, and V. Patel. Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments. $$Proc. London Math. Soc.$$, 109:733-762, 2014. · Zbl 1302.05069 [125] D. Kühn, R. Mycroft, and D. Osthus. A proof of Sumner’s universal tournament conjecture for large tournaments. $$Proc. London Math. Soc.$$, 102:731-766, 2011. · Zbl 1218.05034 [126] D. Kühn and D. Osthus. Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments. $$Adv. Math.$$, 237:62-146, 2013. · Zbl 1261.05053 [127] D. Kühn, D. Osthus, and T. Townsend. Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle length. $$Combinatorica$$, 36:451-469, 2016. · Zbl 1389.05058 [128] M. Kumar and D. Lokshtanov. Faster exact and parameterized algorithm for Feedback Vertex Set in tournaments. In $$STACS 2016: 33rd Symposium on Theoretical Aspects of Computer Science$$, volume 47 of $$LIPIcs$$, pages 49:1-49:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. · Zbl 1388.68324 [129] H.G. Landau. On dominance relations and the structure of animal societies III. The condition for a score structure. $$Bull. Math. Biophys.$$, 15:143-148, 1953. [130] H. Li and J. Shu. The partition of a strong tournament. $$Discrete Math.$$, 290:211-220, 2005. · Zbl 1069.05037 [131] N. Lichiardopol. Proof of a conjecture of Henning and Yeo on vertex-disjoint directed cycles. $$SIAM J. Discrete Math.$$, 28:1618-1627, 2014. · Zbl 1305.05109 [132] N. Lichiardopol. Vertex-disjoint cycles in regular tournaments. $$Discrete Math.$$, 312:1927-1930, 2012. · Zbl 1243.05097 [133] N. Lichiardopol. Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: Proof for tournaments of a conjecture of Stiebitz. $$Intern. J. Combin.$$, Article ID 273416:1-9, 2012. · Zbl 1236.05095 [134] N. Lichiardopol, A. Pór, and J.-S. Sereni. A step towards the Bermond-Thomassen conjecture about disjoint cycles in digraphs. Manuscript, 2007. [135] N. Linial, M. Saks, and V.T. Sós. Largest digraphs contained in all $$\(n$$\)-tournaments. $$Combinatorica$$, 3(1):101-104, 1983. · Zbl 0532.05032 [136] B. Llano and V. Neumann-Lara. Circulant tournaments of prime order are tight. $$Discrete Math.$$, 308:6056-6063, 2008. · Zbl 1198.05083 [137] X. Lu. On avoidable and unavoidable trees. $$J. Graph Theory$$, 22:335-346, 1996. · Zbl 0858.05034 [138] C.L. Lucchesi and D.H. Younger. A minimax theorem for directed graphs. $$J. London Math. Soc. (2)$$, 17(3):369-374, 1978. · Zbl 0392.05029 [139] W. Mader. Critically $$\(n$$\)-connected digraphs. In $$Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988)$$, Wiley-Intersci. Publ., pages 811-829. Wiley, New York, 1991. [140] E.S. Mahmoodian. A critical case method of proof in combinatorial mathematics. $$Bull. Iranian Math. Soc.$$, 8:1L-26L, 1978. [141] M. Mnich, V. Vassilevska Williams, and L.A. Végh. A 7/3-Approximation for Feedback Vertex Sets in Tournaments. In $$The 24th Annual European Symposium on Algorithms (ESA 2016)$$, volume 57 of $$LIPIcs$$, pages 67:1-67:14, 2016. · Zbl 1397.68226 [142] B. Mohar. Circular colorings of edge-weighted graphs. $$J. Graph Theory$$, 43(2):107-116, 2003. · Zbl 1014.05026 [143] J.W. Moon. On maximal transitive subtournaments. $$Proc. Edinburgh Math. Soc. (Ser. 2)$$, 17:345-349, 12 1971. · Zbl 0234.05108 [144] J.W. Moon. On subtournaments of a tournament. $$Can. Math. Bull.$$, 9:297-301, 1966. · Zbl 0141.41204 [145] J.W. Moon. Solution to problem 463. $$Math. Mag.$$, 35:189, 1962. [146] J.W. Moon. $$Topics on tournaments$$. Holt, Rinehart & Winston, New York, 1968. · Zbl 0191.22701 [147] C.St.J.A. Nash-Williams. On orientations, connectivity and odd-vertex-pairings in finite graphs. $$Can. J. Math.$$, 12:555-567, 1960. · Zbl 0096.38002 [148] V. Neumann-Lara. The dichromatic number of a digraph. $$J. Combin. Theory Ser. B.$$, 33:265-270, 1982. · Zbl 0506.05031 [149] V. Neumann-Lara. Vertex critical 4-dichromatic circulant tournaments. $$Discrete Math.$$, 170:289-291, 1997. · Zbl 0876.05039 [150] R. Niedermeier and P. Rossmanith. An efficient fixed-parameter algorithm for 3-hitting set. $$J. Discrete Algor.$$, 1(1):89-102, 2003. · Zbl 1118.68511 [151] V. Petrović. Antidirected Hamiltonian circuits in tournaments. In $$Graph theory (Novi Sad, 1983)$$, pages 259-269. Univ. Novi Sad, Novi Sad, 1984. [152] M. Pilipczuk. Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings. In $$STACS 2013: 30th International Symposium on Theoretical Aspects of Computer Science$$, pages 197-208, 2013. · Zbl 1354.68302 [153] M. Pilipczuk. Computing cutwidth and pathwidth of semi-complete digraphs. In $$Encyclopedia of Algorithms$$, pages 412-415. Springer Verlag, 2016. [154] M. Pilipczuk. $$Tournaments and optimality$$. PhD thesis, University of Bergen, Normay, 2013. [155] A. Pokrovskiy. Edge disjoint Hamilton cycles in highly connected tournaments. $$Intern. Math. Research Notes$$, 2015:19 pp, 2015. [156] A. Pokrovskiy. Highly linked tournaments. $$J. Combin. Theory Ser B$$, 115:339-347, 2015. · Zbl 1319.05063 [157] V. Raman and S. Saurabh. Parameterized complexity of feedback set problems and their duals in tournaments. $$Theor. Comput. Sci.$$, 351:446-458, 2006. · Zbl 1086.68105 [158] L. Rédei. Ein kombinatorischer Satz. $$Acta Litt. Szeged$$, 7:39-43, 1934. [159] B. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals. $$Oper. Res. Lett.$$, 32(4):299-301, 2004. · Zbl 1052.05061 [160] K.B. Reid. Tournaments: scores, kings, generalizations and special topics. $$Congr. Numer.$$, 115:171-211, 1996. Surveys in graph theory (San Francisco, 1995). · Zbl 0899.05024 [161] K.B. Reid. Two complementary circuits in two-connected tournaments. In $$Cycles in graphs (Burnaby, B.C., 1982)$$, volume 115 of $$North-Holland Math. Stud.$$, pages 321-334. North-Holland, 1985. [162] K.B. Reid and E.T. Parker. Disproof of a conjecture of Erdős and Moser on tournaments. $$J. Combin. Theory$$, 9:225-238, 1970. · Zbl 0204.24605 [163] N. Robertson and P.D. Seymour. Graph Minors. XX. Wagner’s conjecture. $$J. Combin. Theory Ser. B$$, 92(2):325-357, 2004. · Zbl 1061.05088 [164] M. Rosenfeld. Antidirected Hamiltonian cycles in tournaments. $$J. Combin. Theory Ser. B$$, 16:234-242, 1974. · Zbl 0279.05111 [165] M. Rosenfeld. Antidirected Hamiltonian paths in tournaments. $$J. Combin. Theory Ser. B$$, 12:93-99, 1971. · Zbl 0229.05119 [166] B. Roy. Nombre chromatique et plus longs chemins d’un graphe. $$Rev. Fr. Inf. Rech. Opér.$$, 1(5):129-132, 1967. · Zbl 0157.31302 [167] A. Sanchez-Flores. On tournaments free of large transitive subtournaments. $$Graphs Combin.$$, 14(2):181-200, 1998. · Zbl 0918.05058 [168] P.D. Seymour. Packing directed circuits fractionally. $$Combinatorica$$, 15(2):281-288, 1995. · Zbl 0826.05031 [169] M.G. Shen. On monochromatic paths in $$\(m$$\)-coloured tournaments. $$J. Combin. Theory Ser. B$$, 45(1):108-111, 1988. · Zbl 0654.05033 [170] B. Smetaniuk. A new construction on Latin squares. $$Ars. Combin.$$, 11:155-172, 1981. [171] Z.M. Song. Complementary cycles of all lengths in tournaments. $$J. Combin. Theory Ser. B$$, 57(1):18-25, 1993. · Zbl 0723.05062 [172] E. Speckenmeyer. On feedback problems in digraphs. In $$WG 1989$$, volume 411 of $$Lect. Notes Comput. Sci.$$, pages 218-231. Springer, 1989. · Zbl 0768.68181 [173] M. Stiebitz. Decomposition of graphs and digraphs. In $$KAM Series in Discrete Mathematics-Combinatorics-Operations Research-Optimization 95-309$$. Charles University Prague, 1995. [174] H.J. Straight. The existence of certain type of semi-walks in tournaments. $$Congr. Numer.$$, 29:901-908, 1980. [175] B.D. Sullivan. A summary of problems and results related to the Caccetta-Haggkvist conjecture. arXiv:math/0605646, May 2006. [176] A. Thomason. Paths and cycles in tournaments. $$Trans. Amer. Math. Soc.$$, 296(1):167-180, 1986. · Zbl 0599.05026 [177] C. Thomassen. Antidirected Hamilton circuits and paths in tournaments. $$Math. Ann.$$, 201:231-238, 1973. · Zbl 0241.05109 [178] C. Thomassen. Configurations in graphs of large minimum degree, connectivity, or chromatic number. $$Annals of the New York Academy of Sciences$$, 555:402-412, 1989. [179] C. Thomassen. Connectivity in tournaments. In $$Graph theory and combinatorics (Cambridge, 1983)$$, pages 305-313. Academic Press, 1984. [180] C. Thomassen. Disjoint cycles in digraphs. $$Combinatorica$$, 3(3-4):393-396, 1983. · Zbl 0527.05036 [181] C. Thomassen. Edge-disjoint Hamiltonian paths and cycles in tournaments. $$Proc. London Math. Soc. (3)$$, 45(1):151-168, 1982. · Zbl 0486.05049 [182] C. Thomassen. Graph decomposition with constraints on the connectivity and minimum degree. $$J. Graph Theory$$, 7:165-167, 1983. · Zbl 0515.05045 [183] C. Thomassen. Hamilton circuits in regular tournaments. In $$Cycles in graphs (Burnaby, B.C., 1982)$$, volume 115 of $$North-Holland Math. Stud.$$, pages 159-162. North-Holland, 1985. [184] C. Thomassen. Hamiltonian-connected tournaments. $$J. Combin. Theory Ser. B$$, 28(2):142-163, 1980. · Zbl 0435.05026 [185] C. Thomassen. Landau’s characterization of tournament score sequences. In $$The theory and applications of graphs (Kalamazoo, Mich., 1980)$$, pages 589-591. Wiley, New York, 1981. [186] C. Thomassen. Strongly 2-connected orientations of graphs. $$J. Combin. Theory Ser. B$$, 110:67-78, 2015. · Zbl 1302.05096 [187] C. Thomassen. The $$\(2$$\)-linkage problem for acyclic digraphs. $$Discrete Math.$$, 55(1):73-87, 1985. · Zbl 0563.05027 [188] F. Tian, Z.S. Wu, and C.Q. Zhang. Cycles of each length in tournaments. $$J. Combin. Theory Ser. B$$, 33(3):245-255, 1982. · Zbl 0495.05028 [189] T.W. Tillson. A Hamiltonian decomposition of $$\({K}^{^{⁎ } }_{2m}$$\), $$\(2m\ge 8$$\). $$J. Combin. Theory Ser. B$$, 29(1):68-74, 1980. · Zbl 0439.05025 [190] A. van Zuylen and D.P. Williamson. Deterministic pivoting algorithms for constrained ranking and clustering problems. $$Math. Oper. Res.$$, 34(3):594-620, 2009. · Zbl 1216.68343 [191] L.M. Vitaver. Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix. $$Dokl. Akad. Nauk SSSR$$, 147:758-759, 1962. · Zbl 0126.39302 [192] M. Welhan. The Hoàng-Reed Conjecture for $$\(δ ^+=3$$\) . $$Discrete Math.$$, 310(13-14):1932 -1939, 2010. · Zbl 1222.05091 [193] Z.S. Wu, K.M. Zhang, and Y. Zou. A necessary and sufficient condition for arc-pancyclicity of tournaments. $$Sci. Sinica Ser. A$$, 25:249-254, 1982. · Zbl 0485.05029 [194] T. Yao, Y. Guo, and K. Zhang. Pancyclic out-arcs of a vertex in a tournament. $$Discrete Appl. Math.$$, 99:245-249, 2000. · Zbl 0939.05045 [195] A. Yeo. The number of pancyclic arcs in a $$\(k$$\)-strong tournament. $$J. Graph Theory$$, 50:211-219, 2005. · Zbl 1081.05041 [196] C.Q. Zhang. Every regular tournament has two arc-disjoint hamiltonian cycles. $$J. Qufu Normal College$$, Special Issue Oper. Res.:70-81, 1980.
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.