Signed Gyárfás–Sumner conjecture

About 1 year old · traced to

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.

References

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.