Open Research Index

Set-defined graph classes: $χ$-boundedness meets tropical algebra

Sarosh Adenwalla, Samuel Braunfeld, Tomáš Hons, John Sylvester, Viktor Zamaraev

arXivarxiv/2607.23754Jul 26, 2026cs.DMscore 0

We study set-defined graph classes: hereditary classes whose vertices are assigned fixed-length numerical tuples, with adjacency determined solely by equality patterns among coordinates. These classes arise in structural graph theory, communication complexity, logic, and adjacency labeling schemes. We ask when they are $χ$-bounded, that is, when chromatic number is bounded in terms of clique number throughout the class. First, we prove a decomposition theorem: every graph in a set-defined class can be partitioned into a number of parts polynomially bounded in its clique number, each inducing…

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