Bounded neighborhoods in K4-free, induced-path-free signed graphs

From papers

For a signed graph G^\widehat{G} and a vertex uu, let N[u]N[u] denote the closed neighborhood of uu, and let χb\chi_b denote balanced chromatic number. Bounded-neighborhood conjecture. For every positive integer kk, there exists a positive integer bkb_k such that, whenever

G^Forbind({(K4,)^,Pk}),\widehat{G}\in\operatorname{Forb}_{ind}(\{\widehat{(K_4,-)},P_k\}),

every vertex uu of G^\widehat{G} has closed neighborhood satisfying

χb(N[u])bk.\chi_b(N[u])\leq b_k.

This conjecture is presented as an equivalent relaxation of the conjecture for arbitrary linear forests: the paper proves that such a neighborhood bound yields a global balanced-coloring bound. 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.