An Erdos-Gallai conjecture for signed graphs

Abstract

For every natural number $p$, we show that the maximum negative girth among the class of signed graphs on $n$ vertices with balanced chromatic number at least $p$ is between $(1/e)n^{1/(p-1)}$ and $2(p-1)n^{1/(p-1)}$. This extends a conjecture of Erdős and Gallai to signed graphs.