5 papers · 1 filter
Coloring t-perfect graphs with fewer colors
Matija Novaković, Stefan Weltge
Recently, Chudnovsky, Cook, Davies, Oum, and Tan obtained the first finite bound on the chromatic number of t-perfect graphs, showing that they are 199053-colorable. We improve thi…
On the number of finite additive 2-bases
Stefan Weltge, Konrad Zyhalko
The number of finite additive 2-bases is known to grow exponentially. While this fact has been established by Marzuola and Miller (2010) using complex analytic techniques embedded…
Integer programs with nearly totally unimodular matrices: the cographic case
Manuel Aprile, Samuel Fiorini, Gwenaël Joret +4
It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix whose subdeterminants are all bounded by a constant in absolute value, ca…
Binary scalar products
Andrey Kupavskii, Stefan Weltge
Let both span such that holds for all , . We show that $ |A| \cdot |B| \le (d+1) 2…
Tight bounds on discrete quantitative Helly numbers
Gennadiy Averkov, Bernardo González Merino, Matthias Henze +2
Given a subset S of R^n, let c(S,k) be the smallest number t such that whenever finitely many convex sets have exactly k common points in S, there exist at most t of these sets tha…