Bounded neighborhoods in K4-free, induced-path-free signed graphs
Bounded neighborhoods in K4-free, induced-path-free signed graphs
For a signed graph and a vertex , let denote the closed neighborhood of , and let denote balanced chromatic number. Bounded-neighborhood conjecture. For every positive integer , there exists a positive integer such that, whenever
every vertex of has closed neighborhood satisfying
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
Sign in to submit a solution.
No solutions have been posted yet.