Minimal signed Gyárfás–Sumner sets containing a negative edge
Minimal signed Gyárfás–Sumner sets containing a negative edge
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 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
Sign in to submit a solution.
No solutions have been posted yet.