Minimal signed Gyárfás–Sumner sets containing a negative edge

From papers

Let a finite set of signed graphs be a GS set when its forbidden induced-subgraph class has bounded balanced chromatic number, and call it minimal if no proper subset is a GS set. Minimal-set conjecture. Any minimal finite GS set containing (K2,)^\widehat{(K_2,-)} has exactly three elements.

This statement is the signed formulation of the classical Gyárfás–Sumner conjecture for the hereditary class corresponding to graphs with no negative simple edge. The paper presents it as an open conjectural description of minimal finite GS sets.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Guillaume Aubian, Allen Ibiapina, Luis Kuffner, Reza Naserasr, Cyril Pujol, Cléophée Robin and Huan Zhou, “Extension of the Gyárfás-Sumner conjecture to signed graphs”, arXiv:2511.03335 (2025).

Solutions 0

No solutions have been posted yet.