Cover Image

Maker-Breaker is solved in polynomial time on hypergraphs of rank 3

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Galliot, Florian, Gravier, Sylvain, Sivignon, Isabelle
Format:	Preprint
Published:	2022
Subjects:	Discrete Mathematics Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Some polynomial classes for the acyclic orientation with parity constraint problem
by: Gravier, Sylvain, et al.
Published: (2026)

4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
by: Galliot, Florian
Published: (2025)

Note about the complexity of the acyclic orientation with parity constraint problem
by: Gravier, Sylvain, et al.
Published: (2025)

Maker-Maker games of rank 4 are PSPACE-complete
by: Galliot, Florian, et al.
Published: (2025)

The Avoider-Enforcer game on hypergraphs of rank 3
by: Galliot, Florian, et al.
Published: (2025)

A unified convention for achievement positional games
by: Galliot, Florian, et al.
Published: (2025)

On the complexity of the Maker-Breaker happy vertex game
by: Hilaire, Mathieu, et al.
Published: (2026)

On the parameterized complexity of the Maker-Breaker domination game
by: Bagan, Guillaume, et al.
Published: (2026)

Solving Maker-Breaker Games on 5-uniform hypergraphs is PSPACE-complete
by: Koepke, Finn Orson
Published: (2025)

Token positional games
by: Bagan, Guillaume, et al.
Published: (2026)

Partition strategies for the Maker-Breaker domination game
by: Bagan, Guillaume, et al.
Published: (2024)

Octal Games on Graphs: The game 0.33 on subdivided stars and bistars
by: Beaudou, Laurent, et al.
Published: (2016)

Three-chromatic geometric hypergraphs
by: Damásdi, Gábor, et al.
Published: (2021)

On arborescence packing augmentation in hypergraphs
by: Hoppenot, Pierre, et al.
Published: (2024)

A two-player version of the assignment problem
by: Galliot, Florian, et al.
Published: (2026)

The chromatic number of triangle-free hypergraphs
by: Li, Lina, et al.
Published: (2022)

Balanced colorings of Erdős-Rényi hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2025)

Balanced independent sets and colorings of hypergraphs
by: Dhawan, Abhishek
Published: (2023)

A note on hypergraphs with asymmetric Ramsey properties
by: Sviridenkov, Vladimir
Published: (2026)

Chemically inspired Erdős-Rényi oriented hypergraphs
by: Garcia-Chung, Angel, et al.
Published: (2023)

Regular packing of rooted hyperforests with root constraints in hypergraphs
by: Hoppenot, Pierre, et al.
Published: (2023)

Note on polychromatic coloring of hereditary hypergraph families II
by: Pálvölgyi, Dömötör
Published: (2026)

The convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flores Theorem
by: Martínez-Sandoval, Leonardo, et al.
Published: (2019)

Efficient polynomial-time approximation scheme for the genus of dense graphs
by: Jing, Yifan, et al.
Published: (2020)

Characterizing the optimum bases of a convex geometry using quasi-closed hypergraphs
by: Meunier, Anthony, et al.
Published: (2026)

Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
by: Jedličková, Nikola, et al.
Published: (2023)

On approximating the rank of graph divisors
by: Bérczi, Kristóf, et al.
Published: (2022)

Augmenting a hypergraph to have a matroid-based $(f,g)$-bounded $(α,β)$-limited packing of rooted hypertrees
by: Hoppenot, Pierre, et al.
Published: (2024)

Unavoidable butterfly minors in digraphs of large cycle rank
by: Hatzel, Meike, et al.
Published: (2025)

Bounded twin-width graphs are polynomially $χ$-bounded
by: Bourneuf, Romain, et al.
Published: (2023)

Interaction between skew-representability, tensor products, extension properties, and rank inequalities
by: Bérczi, Kristóf, et al.
Published: (2025)

A polynomial bound for the minimal excluded minors for a surface
by: Houdaigoui, Sarah, et al.
Published: (2026)

A quasi-polynomial bound for the minimal excluded minors for a surface
by: Houdaigoui, Sarah, et al.
Published: (2025)

Poset Positional Games
by: Bagan, Guillaume, et al.
Published: (2024)

A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths
by: Baste, Julien, et al.
Published: (2025)

Geodetic Graphs: Experiments and New Constructions
by: Stober, Florian, et al.
Published: (2023)

Complexity results on the decomposition of a digraph into directed linear forests and out-stars
by: Hörsch, Florian, et al.
Published: (2024)

Increasing arc-connectivity by bounded- and fixed-size inversions
by: Hörsch, Florian, et al.
Published: (2026)

Counting simplicial pairs in hypergraphs
by: Barrett, Jordan, et al.
Published: (2024)

Diameter of the inversion graph
by: Havet, Frédéric, et al.
Published: (2024)