2 papers
cs.DS2025
A Near-Optimal Kernel for a Coloring Problem
Ishay Haviv, Dror Rabinovich
For a fixed integer , the -Coloring problem asks to decide if a given graph has a vertex coloring with colors such that no two adjacent vertices receive the same color. I…
cs.DS2024
Kernelization for Orthogonality Dimension
Ishay Haviv, Dror Rabinovich
The orthogonality dimension of a graph over is the smallest integer for which one can assign to every vertex a nonzero vector in such that every two…