{"id":"arxiv/2608.08799","url":"https://arxiv.org/abs/2608.08799","tags":["math.CO"],"score":0,"title":"The $Δ$-Conjecture for CIS $d$-Graphs","domain":"math.CO","source":"arxiv","authors":["Yinchen Liu","Quanyu Tang"],"reviews":0,"subject":"math.CO","summary":"We prove the $Δ$-conjecture, which dates back to Gurvich's 1978 thesis. Specifically, let the edges of a complete graph be colored with colors $1,\\ldots,d$, and for each $i$ let $G_i$ be the graph on the same vertex set formed by the edges of color $i$. We prove that if every choice of a maximal stable set $S_i$ of $G_i$, one for each $i\\in[d]$, has nonempty intersection, then the coloring contains no rainbow triangle. Together with a result of Andrade, Boros, and Gurvich, this characterizes CIS $d$-graphs as precisely the Gallai $d$-graphs whose chromatic components are ordinary CIS graphs.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-09","reactions":{}}