K4-free signed Gyárfás–Sumner conjecture for linear forests

From papers

Let FF be a linear forest, meaning a forest whose connected components are paths. Let (K4,)^\widehat{(K_4,-)} be the specified signed complete graph, and call a finite set of signed graphs a GS set when the corresponding forbidden induced-subgraph class has bounded balanced chromatic number. K4-free signed Gyárfás–Sumner conjecture. For every linear forest FF, the set

{(K4,)^,F}\{\widehat{(K_4,-)},F\}

is a GS set.

The paper proves that being a linear forest is necessary and proves the claim when every component of FF is a path of length at most 44. Sufficiency for arbitrary linear forests is left 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.