The $\Delta$-Conjecture for CIS $d$-Graphs

Abstract

We prove the $\Delta$-conjecture, which dates back to Gurvich's 1978 thesis. Specifically, let the edges of a complete graph be colored with colors $1,\dots ,d$, and for each $i$ let $G_i$ be the graph 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.

5 pages. Comments and suggestions are welcome