An Erdos-Gallai conjecture for signed graphs

2025/09/09 by Wang, Lujia
#05C15 #05C22 #05C38 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2509.07724

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.

Related

• A note on generalized chromatic number and generalized girth
• The rank of a signed graph in terms of girth
• Connected signed graphs with given inertia indices and given girth
• Ramsey-type numbers involving graphs and hypergraphs with large girth
• The chromatic number of signed graphs with bounded maximum average degree