On some k-fold generalizations of Lovász theta and their sandwich theorems
We study several $k$-fold generalizations of the Lovász theta function associated with the maximum $k$-colorable induced subgraph problem. The first is the Narasimhan--Manber parameter $\vartheta_k$. We prove that, for graphs whose adjacency matrix belongs to a homogeneous partially coherent algebra, this parameter is recovered by the theta number of the Cartesian product with the complete graph on $k$ vertices. This class includes distance-regular and $1$-walk-regular graphs, and thus our result generalizes a theorem by Sinjorgo and Sotirov (2022) for graphs that are vertex- and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.06312
curl -X POST /api/v1/records/arxiv/2609.06312/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.06312/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'