{"id":"arxiv/2608.22350","url":"https://arxiv.org/abs/2608.22350","tags":["math.CO"],"score":0,"title":"Ramsey-type results for threshold graphs and beyond","domain":"math.CO","source":"arxiv","authors":["Xihe Li"],"reviews":0,"subject":"math.CO","summary":"A {\\it threshold graph} is a graph that can be constructed from the one-vertex graph by repeatedly adding either a dominating vertex or an isolated vertex. Motivated by an induced Ramsey-type problem for this class, we define $r'_2(s)$ to be the minimum integer $n$ such that every $n$-vertex graph contains an induced threshold graph on $s$ vertices. We establish exponential upper and lower bounds for $r'_2(s)$ and determine its exact values for $s\\in\\{3,4,5,6\\}$. To study this problem from an edge-coloring perspective, we use the notion of an orderable coloring, introduced by Richer [{\\it J.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-23","reactions":{}}