Signed Gyárfás–Sumner conjecture
Signed Gyárfás–Sumner conjecture
Let and let denote the signed graph obtained from a graph by replacing each edge with a digon. A finite set of signed graphs is a GS set when its forbidden induced-subgraph class has bounded balanced chromatic number. Signed Gyárfás–Sumner conjecture. For every forest and complete graph , the set
is a GS set.
Balanced coloring extends ordinary proper coloring: . Thus this is a direct signed-graph restatement of the classical Gyárfás–Sumner conjecture, and it remains open.
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.