Cover Image

Finding forest-orderings of tournaments is NP-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aboulker, Pierre, Aubian, Guillaume, Lopes, Raul
Format:	Preprint
Published:	2024
Subjects:	Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computing the clique number of tournaments
by: Aubian, Guillaume
Published: (2024)

Blow-ups and extensions of trees in tournaments
by: Aboulker, Pierre, et al.
Published: (2024)

(Claw, C_3)-free digraphs with unbounded dichromatic number
by: Aubian, Guillaume, et al.
Published: (2026)

Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order
by: Aboulker, Pierre, et al.
Published: (2024)

Computing the degreewidth of a digraph is hard
by: Aboulker, Pierre, et al.
Published: (2024)

On cuts of small chromatic number in sparse graphs
by: Aubian, Guillaume, et al.
Published: (2025)

Partitioning a tournament into sub-tournaments of high connectivity
by: Girão, António, et al.
Published: (2022)

On 5-cycles and strong 5-subtournaments in a tournament of odd order n
by: Savchenko, Sergey
Published: (2024)

Cyclic subsets of tournaments
by: Hunter, Zach, et al.
Published: (2025)

Hamilton transversals in tournaments
by: Chakraborti, Debsoumya, et al.
Published: (2023)

Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
by: Aubian, Guillaume, et al.
Published: (2025)

Induced Disjoint Paths Without an Induced Minor
by: Aboulker, Pierre, et al.
Published: (2025)

Finding subdigraphs in digraphs of bounded directed treewidth
by: Lopes, Raul, et al.
Published: (2025)

Tournament completions of bipartite tournaments and their augmented directed cycles
by: Wong, H. W. Willie
Published: (2024)

Transversal cycles and paths in tournaments
by: Chakraborti, Debsoumya, et al.
Published: (2024)

Variations on Sidorenko's conjecture in tournaments
by: Fox, Jacob, et al.
Published: (2024)

Undecidability of polynomial inequalities in tournaments
by: Chen, Hao, et al.
Published: (2024)

Trees with many leaves in tournaments
by: Benford, Alistair, et al.
Published: (2022)

Immersions of directed graphs in tournaments
by: Girão, António, et al.
Published: (2023)

Extension of the Gyárfás-Sumner conjecture to signed graphs
by: Aubian, Guillaume, et al.
Published: (2025)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

Invertibility of digraphs and tournaments
by: Alon, Noga, et al.
Published: (2022)

New Sidorenko-type inequalities in tournaments
by: He, Xiaoyu, et al.
Published: (2025)

Color-avoiding directed paths in tournaments
by: Fox, Jacob, et al.
Published: (2025)

The dimension of the region of feasible tournament profiles
by: Kral, Daniel, et al.
Published: (2023)

Some results and problems on tournament structure
by: Nguyen, Tung, et al.
Published: (2023)

Hamilton decompositions of regular tripartite tournaments
by: Di Braccio, Francesco, et al.
Published: (2025)

Sidorenko property and forcing in regular tournaments
by: Král', Daniel, et al.
Published: (2026)

On the number of 8-cycles for two particular regular tournaments of order N with diametrically opposite local properties
by: Savchenko, Sergey
Published: (2024)

Intransitive dice tournament is not quasirandom
by: Cornacchia, Elisabetta, et al.
Published: (2020)

Unavoidable structures in infinite tournaments
by: Benford, Alistair, et al.
Published: (2023)

Vertex-disjoint cycles of different lengths in tournaments
by: Bai, Yandong, et al.
Published: (2024)

A new perspective from hypertournaments to tournaments
by: Ai, Jiangdong, et al.
Published: (2024)

Acyclic subgraphs of tournaments with high chromatic number
by: Fox, Jacob, et al.
Published: (2019)

Strong chordality in tournaments and multipartite tournaments with possible loops
by: Hell, Pavol, et al.
Published: (2025)

Almost colour-balanced spanning forests in complete graphs
by: Hollom, Lawrence, et al.
Published: (2024)

Schuttes property for sets of tournaments and an application to dice games
by: Jeffries, Joel
Published: (2026)

The structure of $Δ(1, 2, 2)$-free tournaments
by: Kim, Seokbeom, et al.
Published: (2025)

A Gray code for arborescences of tournaments
by: Bonamy, Marthe, et al.
Published: (2026)

Solution on strong partition of $2$-balanced regular multipartite tournaments
by: Ai, Jiangdong, et al.
Published: (2024)