{"id":"arxiv/2608.06055","url":"https://arxiv.org/abs/2608.06055","tags":["cs.DM","cs.DS","math.CO"],"score":0,"title":"Simultaneous Graph Parameters and How to Bound Them","domain":"cs.DM","source":"arxiv","authors":["Robert Scheffler","Philipp Wolf Schleicher"],"reviews":0,"subject":"cs.DM","summary":"Beisegel et al. [SWAT 2024] introduced the concept of simultaneous $\\mathcal{C}$-numbers which associate a graph class $\\mathcal{C}$ with a graph parameter. Given a graph $G$, the simultaneous $\\mathcal{C}$-number is the smallest number $d$ for which there is a graph $H \\in \\mathcal{C}$ and a function $L : V(G) \\to \\mathcal{P}(\\{1,\\dots,d\\})$ such that two vertices $u$ and $v$ are adjacent in $G$ if and only if they are adjacent in $H$ and their sets $L(u)$ and $L(v)$ are not disjoint. We study the relation of these simultaneous $\\mathcal{C}$-numbers to other graph parameters. In particular,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-06","reactions":{}}