K4-free signed Gyárfás–Sumner conjecture for linear forests
K4-free signed Gyárfás–Sumner conjecture for linear forests
Let be a linear forest, meaning a forest whose connected components are paths. Let 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 , the set
is a GS set.
The paper proves that being a linear forest is necessary and proves the claim when every component of is a path of length at most . 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
Sign in to submit a solution.
No solutions have been posted yet.