Signed Gyárfás–Sumner conjecture

From papers

Let K^2=(K2,)^\widehat{K}_2^- = \widehat{(K_2,-)} and let G~\widetilde{G} denote the signed graph obtained from a graph GG 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 FF and complete graph KtK_t, the set

{(K2,)^,K~t,F~}\{\widehat{(K_2,-)},\widetilde{K}_t,\widetilde{F}\}

is a GS set.

Balanced coloring extends ordinary proper coloring: χb(G~)=χ(G)\chi_b(\widetilde{G})=\chi(G). 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

No solutions have been posted yet.