The $Δ$-Conjecture for CIS $d$-Graphs

Abstract

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 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.

Disclosure

“Statement on AI usage The main proof strategy, in particular the inductive use of the local configuration around a rainbow triangle together with restriction to a proper induced subgraph, was developed by the authors. ChatGPT was used during the preparation of the manuscript to assist with some technical details, including parts of the proof of Lemma 2.1. It was also used to help check and polish some arguments. All AI-assisted arguments were independently veri”

PDF page 5

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:06:11.772819Z

Structural counts