Cover Image

The Borsuk number of a graph

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cáceres, José, Garijo, Delia, Márquez, Alberto, Silveira, Rodrigo I.
Format:	Preprint
Published:	2026
Subjects:	Combinatorics Computational Complexity Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the complexity of covering points by guillotine cuts
by: Garijo, Delia, et al.
Published: (2026)

Undecidability of tiling the plane with a fixed number of Wang bars
by: Yang, Chao, et al.
Published: (2024)

Undecidability of Translational Tiling with Three Tiles
by: Yang, Chan, et al.
Published: (2024)

Translational Aperiodic Sets of 7 Polyominoes
by: Yang, Chao, et al.
Published: (2024)

Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
by: Yang, Chao, et al.
Published: (2024)

Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
by: Yang, Chao, et al.
Published: (2024)

A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes
by: Yang, Chao, et al.
Published: (2024)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
by: Yang, Chao, et al.
Published: (2024)

Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)

Bounds for Geometric rank in Terms of Subrank
by: Chen, Qiyuan, et al.
Published: (2025)

The Tensor as an Informational Resource
by: Christandl, Matthias
Published: (2023)

Between proper and square coloring of planar graphs, hardness and extremal graphs
by: Delépine, Thomas
Published: (2026)

Sensitivity and Hamming graphs
by: Asensio, Sara, et al.
Published: (2025)

Gromov's Approximating Tree and the All-Pairs Bottleneck Paths Problem
by: Cornect, Anders, et al.
Published: (2024)

$C_{2k+1}$-coloring of bounded-diameter graphs
by: Piecyk, Marta
Published: (2024)

The metric Menger problem
by: Baligács, Júlia, et al.
Published: (2024)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
by: Gan, Luyining, et al.
Published: (2023)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
by: Dorfer, Joseph
Published: (2026)

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
by: Dakhno, Grigorii, et al.
Published: (2024)

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
by: Hodur, Nadzieja, et al.
Published: (2025)

Bounding and computing obstacle numbers of graphs
by: Balko, Martin, et al.
Published: (2022)

On the rectilinear crossing number of complete balanced multipartite graphs and layered graphs
by: Fabila-Monroy, Ruy, et al.
Published: (2024)

On the hull and interval numbers of oriented graphs
by: Araujo, J., et al.
Published: (2022)

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

Combinatorial refinement on circulant graphs
by: Kluge, Laurence
Published: (2022)

Sublevels in arrangements and the spherical arc crossing number of complete graphs
by: Streltsova, Elizaveta, et al.
Published: (2025)

Complexity results for a cops and robber game on directed graphs
by: Ben-Ameur, Walid, et al.
Published: (2024)

On the complexity of global Roman domination problem in graphs
by: Reddy, Sangam Balchandar, et al.
Published: (2026)

On full-separating sets and related codes in graphs
by: Chakraborty, Dipayan, et al.
Published: (2024)

Temporal Reachability Dominating Sets: contagion in temporal graphs
by: Kutner, David C., et al.
Published: (2023)

A structural description of Zykov and Blanche Descartes graphs
by: Marin, Malory, et al.
Published: (2024)

On the hardness of recognizing graphs of small mim-width and its variants
by: la Tour, Max Dupré, et al.
Published: (2025)

Random regular graph states are complex at almost any depth
by: Ghosh, Soumik, et al.
Published: (2024)

On a Hierarchy of Spectral Invariants for Graphs
by: Arvind, V., et al.
Published: (2023)

Hunting a rabbit: complexity, approximability and some characterizations
by: Ben-Ameur, Walid, et al.
Published: (2025)

Finding a HIST: Chordality, Structural Parameters, and Diameter
by: Hanaka, Tesshu, et al.
Published: (2025)

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
by: Le, Hoang-Oanh, et al.
Published: (2023)

Smoothed analysis for graph isomorphism
by: Anastos, Michael, et al.
Published: (2024)

Borsuk's conjecture for two-distance sets and its equivalent formulation for graphs
by: Musin, Oleg R.
Published: (2025)