Tournaments and Semicomplete Digraphs
From MaRDI portal
Publication:3120434
DOI10.1007/978-3-319-71840-8_2zbMath1407.05102OpenAlexW2808898944MaRDI QIDQ3120434
Frédéric Havet, Jörgen Bang-Jensen
Publication date: 4 March 2019
Published in: Springer Monographs in Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-71840-8_2
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Directed graphs (digraphs), tournaments (05C20)
Related Items (13)
Vertex-disjoint cycles of different lengths in multipartite tournaments ⋮ Every \((13k - 6)\)-strong tournament with minimum out-degree at least \(28k - 13\) is \(k\)-linked ⋮ On \(d\)-panconnected tournaments with large semidegrees ⋮ Semicomplete compositions of digraphs ⋮ Hamiltonicity, pancyclicity, and full cycle extendability in multipartite tournaments ⋮ Vertex-disjoint cycles of different lengths in local tournaments ⋮ On Seymour's and Sullivan's second neighbourhood conjectures ⋮ Paths with many shortcuts in tournaments ⋮ Pancyclicity in strong \(k\)-quasi-transitive digraphs of large diameter ⋮ Spanning Eulerian subdigraphs avoiding \(k\) prescribed arcs in tournaments ⋮ Oriented bipartite graphs and the Goldbach graph ⋮ Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs ⋮ Tournaments and Bipartite Tournaments without Vertex Disjoint Cycles of Different Lengths
Cites Work
- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
- A Min-Max Theorem on Tournaments
- A Step toward the Bermond–Thomassen Conjecture about Disjoint Cycles in Digraphs
- An exact minimum degree condition for Hamilton cycles in oriented graphs
- Fast FAST
- Graph decomposition with constraints on the connectivity and minimum degree
- On the existence of specified cycles in a tournament
- Paths and Cycles in Tournaments
- Cycles in digraphs– a survey
- Long paths and cycles in oriented graphs
- Paley graphs satisfy all first-order adjacency axioms
- Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
- A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs
- A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
- Diconnected Orientations and a Conjecture of Las Vergnas
- A Minimax Theorem for Directed Graphs
- Generalizations of tournaments: A survey
- Hamilton Cycles in Oriented Graphs
- Hamiltonian Cycles Avoiding Prescribed Arcs in Tournaments
- Color-coding
- Adding and Reversing Arcs in Semicomplete Digraphs
- Circular colorings of edge-weighted graphs
- Short proofs of classical theorems
- Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture
- Cycles with two blocks in k‐chromatic digraphs
- A 7/3-Approximation for Feedback Vertex Sets in Tournaments
- Edge Disjoint Hamiltonian Cycles in Highly Connected Tournaments
- Strong immersion is a well‐quasi‐ordering for semicomplete digraphs
- Subdivisions of oriented cycles in digraphs with large chromatic number
- Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments
- Quasi‐transitive digraphs
- Feedback Vertex Sets in Tournaments
- Reducibility among Combinatorial Problems
- Out‐colourings of digraphs
- Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs
- Triangle packing in (sparse) tournaments: approximation and kernelization
- Remarks on the second neighborhood problem
- About paths with two blocks
- Sparse Spanning $k$-Connected Subgraphs in Tournaments
- Disjoint 3‐Cycles in Tournaments: A Proof of The Bermond–Thomassen Conjecture for Tournaments
- Ranking Tournaments
- Digraphs
- On Subtournaments of a Tournament
- Cycles of Each Length in Regular Tournaments
- Nombre chromatique et plus longs chemins d'un graphe
- Disproof of a conjecture of Erdös and moser on tournaments
- Zur algebraischen Begründung der Graphentheorie. I
- On maximal transitive subtournaments
- The number of pancyclic arcs in a k‐strong tournament
- Jungles, bundles, and fixed-parameter tractability
- Aggregating inconsistent information
- Trees in tournaments
- Trees in tournaments
- Antidirected Hamiltonian paths in tournaments
- Antidirected Hamiltonian paths in tournaments
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding good 2-partitions of digraphs. I. Hereditary properties
- Bipartitions of highly connected tournaments
- The number of Seymour vertices in random tournaments and digraphs
- Vertex-disjoint cycles in regular tournaments
- Edge-disjoint paths in digraphs with bounded independence number
- Strongly 2-connected orientations of graphs
- Disjoint paths in tournaments
- Highly linked tournaments
- Decomposing \(k\)-arc-strong tournaments into strong spanning subdigraphs
- A note on short cycles in digraphs
- Disjoint cycles in digraphs
- A well-quasi-order for tournaments
- Kernels for feedback arc set in tournaments
- Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of Stiebitz
- Finding odd cycle transversals.
- Graph minors. XX: Wagner's conjecture
- Out-arc pancyclicity of vertices in tournaments
- The number of out-pancyclic vertices in a strong tournament
- Tournament pathwidth and topological containment
- Complementary cycles of all lengths in tournaments
- On the maximum cardinality of a consistent set of arcs in a random tournament
- Largest digraphs contained in all n-tournaments
- Parameterized algorithms for feedback set problems and their duals in tournaments
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- An efficient fixed-parameter algorithm for 3-hitting set
- Paths with two blocks in \(n\)-chromatic digraphs
- Powers of Hamilton cycles in tournaments
- Hoàng-Reed conjecture holds for tournaments
- A conjecture of Neumann-Lara on infinite families of \(r\)-dichromatic circulant tournaments
- Spanning 2-strong tournaments in 3-strong semicomplete digraphs
- The Hoàng-Reed conjecture for \(\delta ^{+}=3\)
- Circulant tournaments of prime order are tight
- Landau's and Rado's theorems and partial tournaments
- Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs
- The 2-linkage problem for acyclic digraphs
- Hamiltonian dicycles avoiding prescribed arcs in tournaments
- On monochromatic paths in m-coloured tournaments
- Edge-disjoint in- and out-branchings in tournaments and related path problems
- Quick approximation to matrices and applications
- Disjoint directed cycles
- The directed subgraph homeomorphism problem
- Hamiltonian-connected tournaments
- A Hamiltonian decomposition of \(K^*_{2m},2m\geq 8\)
- Realization of certain generalized paths in tournaments
- Graphs which contain all small graphs
- Cycles of each length in tournaments
- On computing the length of longest increasing subsequences
- Directed vertex-connectivity augmentation
- Vertex critical 4-dichromatic circulant tournaments
- Cycles of all lengths in arc-3-cyclic semicomplete digraphs
- Spanning local tournaments in locally semicomplete digraphs
- Approximating minimum feedback sets and multicuts in directed graphs
- On tournaments free of large transitive subtournaments
- Antidirected Hamiltonian circuits in tournaments
- On unavoidability of trees with \(k\) leaves
- Second neighborhood via first neighborhood in digraphs
- Making a tournament \(k\)-arc-strong by reversing or deorienting arcs.
- Oriented Hamiltonian paths in tournaments: A proof of Rosenfeld's conjecture
- A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
- Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
- Disjoint cycles of different lengths in graphs and digraphs
- Finding complementary cycles in locally semicomplete digraphs
- The partition of a strong tournament
- Degree constrained 2-partitions of semicomplete digraphs
- A counterexample to a conjecture on edge-coloured tournaments
- Trees with three leaves are (\(n+1\))-unavoidable
- The dichromatic number of a digraph
- Oriented Hamiltonian cycles in tournaments
- Directed tree-width
- Partitioning vertices of a tournament into independent cycles
- Paths with two blocks in \(k\)-chromatic digraphs
- Packing directed circuits fractionally
- Minimal edge-coverings of pairs of sets
- Tournaments and colouring
- Oriented trees in digraphs
- Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
- Quasi-hamiltonian paths in semicomplete multipartite digraphs
- Pancyclic out-arcs of a vertex in tournaments
- Tournament minors
- Antidirected Hamilton circuits and paths in tournaments
- Parity of paths and circuits in tournaments
- On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
- Finding good 2-partitions of digraphs. II. Enumerable properties
- An Approximation Algorithm for Feedback Vertex Sets in Tournaments
- Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph
- Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
- Proof of a Conjecture of Henning and Yeo on Vertex-Disjoint Directed Cycles
- Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
- Pancyclic arcs and connectivity in tournaments
- Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
- A proof of Sumner's universal tournament conjecture for large tournaments
- Graph Theory and Probability
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
This page was built for publication: Tournaments and Semicomplete Digraphs
