Cover Image

A note on hardness of promise hypergraph colouring

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Wrochna, Marcin
Format:	Preprint
Published:	2022
Subjects:	Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
by: Nakajima, Tamio-Vesa, et al.
Published: (2025)

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

Soft happy colourings and community structure of networks
by: Shekarriz, Mohammad H., et al.
Published: (2024)

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)

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)

Acyclic colourings of graphs with obstructions
by: Chuet, Quentin, et al.
Published: (2022)

Backbone colouring of chordal graphs
by: Araújo, Júlio, et al.
Published: (2025)

Why Districting Becomes NP-hard
by: Jost, Niklas, et al.
Published: (2025)

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

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

Chromatic discrepancy of locally $s$-colourable graphs
by: Corsini, Timothée, et al.
Published: (2025)

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)

Star colouring and locally constrained graph homomorphisms
by: Antony, Cyriac, et al.
Published: (2023)

On the expressive power of $2$-edge-colourings of graphs
by: Bok, Jan, et al.
Published: (2025)

Maker-Breaker is solved in polynomial time on hypergraphs of rank 3
by: Galliot, Florian, et al.
Published: (2022)

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

New bounds for proper $h$-conflict-free colourings
by: Chuet, Quentin, et al.
Published: (2025)

Faster 3-colouring algorithm for graphs of diameter 3
by: Groenland, Carla, et al.
Published: (2026)

Graceful coloring is computationally hard
by: Antony, Cyriac, et al.
Published: (2024)

Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations
by: Bérczi, Kristóf, et al.
Published: (2025)

Algorithms and hardness for Metric Dimension on digraphs
by: Dailly, Antoine, et al.
Published: (2023)

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

Extended formulations for the multilinear polytope of acyclic hypergraphs
by: Del Pia, Alberto, et al.
Published: (2025)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
by: Ciardo, Lorenzo, et al.
Published: (2023)

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number
by: Pilipczuk, Marcin, et al.
Published: (2023)

Rainbow variations on a theme by Mantel: extremal problems for Gallai colouring templates
by: Falgas-Ravry, Victor, et al.
Published: (2022)

Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
by: Beaudou, Laurent, et al.
Published: (2021)

A note on the Alon-Saks-Seymour problem
by: Fox, Jacob
Published: (2026)

Beyond hypergraph acyclicity: limits of tractability for pseudo-Boolean optimization
by: Del Pia, Alberto, et al.
Published: (2024)

On expectations and variances in the hard-core model on bounded degree graphs
by: Davies, Ewan, et al.
Published: (2025)

A note on embracing exchange sequences in oriented matroids
by: Bérczi, Kristóf, et al.
Published: (2025)

A note on the exact partition polytope of Frieze and Teng
by: Narayanan, Krishna, et al.
Published: (2026)

A note on the distinct distances problem over finite fields
by: Brukhim, Nataly, et al.
Published: (2025)

A characterization of testable hypergraph properties
by: Joos, Felix, et al.
Published: (2017)

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

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