Open Research Index

Spectral bounds for distance coloring and packing parameters of graphs via semidefinite programming

Aida Abiad, Yue Yang, Jiang Zhou

arXivarxiv/2606.04856Jun 3, 2026math.COscore 0

Using methods from spectral graph theory and semidefinite programming, we obtain sharp spectral bounds for several graph parameters related to distance colorings and packing, including the injective chromatic number, the open packing number, the injective chromatic index, and the strong chromatic index. The new spectral bounds improve several existing combinatorial bounds. Furthermore, we apply the obtained eigenvalue bounds on the first two parameters to estimate the code covering number and the open packing number of hypercubes, obtaining new exact values and strengthened bounds regarding…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2606.04856
curl -X POST /api/v1/records/arxiv/2606.04856/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.04856/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'