Kernelization for orthogonality dimension

DOI10.1016/J.JCSS.2026.103757MaRDI QIDQ6859728zbMATH OpenFDO

Authors Ishay Haviv, Dror Rabinovich

Publication date 11 February 2026

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2026.103757

zbMATH Keywords

fixed-parameter tractabilitygraph coloringkernelizationorthogonality dimension

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• Approximating the orthogonality dimension of graphs and hypergraphs
• Data reduction for graph coloring problems
• Graph Classes: A Survey
• Graphs and geometry
• High-Rate Storage Codes on Triangle-Free Graphs
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 5454110 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
• Index Coding With Side Information
• Information flows, graphs and their guessing numbers
• Kernelization Lower Bounds by Cross-Composition
• Kernelization. Theory of parameterized preprocessing
• On problems without polynomial kernels
• On the quantum chromatic number of a graph
• On the Shannon capacity of a graph
• On the subspace choosability in graphs
• Optimal data reduction for graph coloring using low-degree polynomials
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Orthogonal representations and connectivity of graphs
• Orthogonal representations over finite fields and the chromatic number of graphs
• Orthogonal vector coloring
• Parameterized algorithms
• Parameterized complexity of vertex colouring
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Round elimination in exact communication complexity
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Some consequences of non-uniform conditions on uniform classes
• Some structural properties of low-rank matrices related to computational complexity
• Sperner property and finite-dimensional Gorenstein algebras associated to matroids
• The (generalized) orthogonality dimension of (generalized) Kneser graphs: bounds and applications
• The Minrank of Random Graphs

Cited in

(1)

• Kernels for storage capacity and dual index coding

This page was built for publication: Kernelization for orthogonality dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6859728)