2 papers
math.CO2026
Schrijver Number Quasi-Tensorization and Multicolor Ramsey Bounds via Robust OR Polynomials
Ijay Narang, Yukai Tang
We introduce a robust OR polynomial framework for composing positive semidefinite certificates across OR constraints. We demonstrate the power of this method in two applications. T…
cs.DS2026
A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting
Amir Ali Ahmadi, Pravesh K. Kothari, Yukai Tang
We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perf…