Set-defined graph classes: $χ$-boundedness meets tropical algebra
文章简介
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 clas…
作者：Sarosh Adenwalla, Samuel Braunfeld, Tomáš Hons, John Sylvester, Viktor Zamaraev
发表日期：2026-07-26