An Erdős-Gallai conjecture for signed graphs

Lujia Wang · 2025

Read An Erdős-Gallai conjecture for signed graphs by Lujia Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07724.txt.

Introduction

Lujia Wang, writing alone in 2025, extends a conjecture of Erdős and Gallai to signed graphs. A signed graph assigns a plus or minus sign to each edge of a network. The negative girth tracks the shortest cycle whose overall sign is negative. The balanced chromatic number is a coloring measure adapted to the signed setting.

Wang proves a two-sided bound. For every natural number p, consider signed graphs on n vertices with balanced chromatic number at least p. Among them, the maximum negative girth lies between two explicit bounds. Both bounds grow like a small power of n, with the same power. So the growth rate is pinned down up to constant factors. Results of this shape link coloring strength to short negative cycles. They force such cycles to appear once coloring demands grow.

Catalog record

CREATORLujia Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE17 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-07724

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Erdős-Gallai conjecture for signed graphs Lujia Wang Abstract For every natural number p p , we show that the maximum negative girth among the class of signed graphs on n n vertices with balanced chromatic number at least p p is between ( 1 / e ) ​ n 1 / ( p − 1 ) (1/e)n^{1/(p-1)} and 2 ​ ( p − 1 ) ​ n 1 / ( p − 1 ) 2(p-1)n^{1/(p-1)} . This extends a conjecture of Erdős and Gallai to signed graphs. Keywords: balanced coloring, graph coloring, negative cycle, signed graph. MSC codes: 05C15, 05C22, 05C38. 1 Introduction Let \lambda(n,p) be the minimum integer \ell such that every n -vertex graph G with chromatic number at least p contains an odd cycle of length at most \ell . In other words, \lambda(n,p) is the maximum odd girth of the class of graphs on n vertices that has the chromatic number at least p . Erdős and Gallai [ 1 ] conjectured that for fixed p , \lambda(n,p) grows asymptotically at a rate of \Theta(n^{1/(p-2)}) . The conjecture is verified in two directions by Lovász [ 6 ] (independently by Schrijver [ 10 ] ) and Kierstead, Szemerédi, and Trotter [ 4 ] , who showed a lower bound and an upper bound, respectively. Theorem 1.1 . For every fixed p , \lambda(n,p)=\Theta(n^{1/(p-2)}). A signed graph (G,\sigma) is a graph G with a signature function \sigma:E(G)\to\{-,+\} . When the signature function is not specified, a signed graph is often denoted by \widehat{G} . Switching a vertex v\in V(G) is the operation to flip all signs on the edges of \widehat{G} incident to v . A subset B\subseteq V(G) of vertices is balanced if the signature on \widehat{G}[B] can be made all positive by a series of switchings; otherwise it is unbalanced . A balanced p -coloring of \widehat{G} is a function f:V(G)\to[p] such that f^{-1}(i) is a balanced set in \widehat{G} for all i\in[p] . The balanced chromatic number \chi_{b}(\widehat{G}) is the minimum integer p such that \widehat{G} admits a balanced p -coloring. The balanced chromatic number of a signed graph is invariant under switchings. A closed walk in \widehat{G} is positive (negative, respectively) if the product of its edges is positive (negative, respectively). Harary [ 2 ] showed that a set of vertices is balanced in a signed graph if and only if it induces no negative cycles. Hence, for signed graphs, the unbalanced (equivalently, negative) cycles play the role of coloring obstacles for balanced coloring, resembling the case of odd cycles for ordinary coloring. The negative girth , g_{-}(\widehat{G}) , of a signed graph \widehat{G} is the length of a shortest negative cycle in \widehat{G} . Let \lambda_{s}(n,p) be the maximum negative girth among the class of signed graphs on n vertices with the balanced chromatic number at least p . We show a result that is parallel to the Erdős-Gallai conjecture for signed graphs. Theorem 1.2 . For every fixed p , \lambda_{s}(n,p)=\Theta(n^{1/(p-1)}). In particular, (1/e)n^{1/(p-1)}\leq\lambda_{s}(n,p)\leq 2(p-1)n^{1/(p-1)}. 2 The lower bound and Kneser signed graphs Two vertices x,y in a signed graph (G,\sigma) are antitwins if N(x)=N(y):=Z and \sigma(xv)=-\sigma(yv) for all v\in Z . A double switching graph is a signed graph where each vertex has exactly one antitwin. A reduction of a double switching graph is the process of deleting exactly one vertex from each pair of antitwins. Switching a vertex of the reduced graph is the same as replacing it with its antitwin (hence, it is another reduction of the same signed graph). Let positive integers n and k satisfy n\geq k . [\pm n]:=\{\pm 1,\pm 2,\ldots,\pm n\} . A set S is a signed k -subset of [n] if S\subseteq[\pm n] , |S|={k} , and S\cap(-S)=\emptyset . The family of all k -subsets of [n] is denoted by \binom{[n]}{k_{\pm}} . The Kneser signed graph \mathit{KS}(n,k) is the signed graph defined on the vertex set \binom{[n]}{k_{\pm}} where AB is a positive (respectively, negative) edge if A\cap(-B)=\emptyset (respectively, A\cap B=\emptyset ). The subgraph of \mathit{KS}(n,k) induced by alternating k -subsets of [n] is called the Schrijver signed graphs , denoted by \mathit{SS}(n,k) . Both graphs are double switching graphs, hence have a reduction by deleting one of the vertices from each pair of antitwins. The corresponding reductions are denoted by \widehat{\mathit{KS}}(n,k) and \widehat{\mathit{SS}}(n,k) , respectively. Kuffner et al. [ 5 ] proved that the balanced chromatic number \chi_{b}(\mathit{KS}(n,k))=\chi_{b}(\mathit{SS}(n,k))=n-k+1 , and that \widehat{\mathit{SS}}(n,k) is a vertex-critical subgraph of the \widehat{\mathit{KS}}(n,k) . We first determine the negative girth of the Kneser signed graphs. Lemma 2.1 . For all positive integers n and k such that n\geq k , g_{-}(\mathit{SS}(n,k))\geq g_{-}(\mathit{KS}(n,k))=\begin{cases}1+\left\lceil\frac{k}{n-k}\right\rceil&\text{if}\quad n>k,\\ \infty&\text{if}\quad n=k.\end{cases} Proof. The first inequality is clear, as Schrijver signed graphs are induced subgraphs of Kneser signed graphs. So, it is enough to determine the negative girth of Kneser signed graphs. The Kneser signed graph \mathit{KS}(k,k) is balanced, so the negative girth is \infty . If n\geq 2k , then g_{-}(\mathit{KS}(n,k))=2 , since there exist unbalanced digons. So, it suffices to deal with the case where k<n<2k . Since \mathit{KS}(n,k) is a double switching graph, every negative cycle can be switched into an inconsistent cycle , i.e., a negative cycle with exactly one negative edge. So we think of the length of a shortest inconsistent cycle. Let A_{1}A_{2}\ldots A_{\ell}A_{1} be a shortest inconsistent cycle in \mathit{KS}(n,k) , where A_{i}A_{i+1} is positive for i\in[\ell-1] , and A_{1}A_{\ell} is negative. For each i\in[\ell-1] , since A_{i}A_{i+1} is positive, A_{i} is disjoint from -A_{i+1} , which implies that |A_{i+1}\setminus A_{i}|\leq n-k. Hence, we have |A_{\ell}\setminus A_{1}|\leq|A_{2}\setminus A_{1}|+|A_{3}\setminus A_{2}|+\cdots+|A_{\ell}\setminus A_{\ell-1}|\leq(\ell-1)(n-k). On the other hand, A_{\ell} and A_{1} are disjoint, since A_{1}A_{\ell} is a negative edge. So, k=|A_{\ell}|=|A_{\ell}\setminus A_{1}|\leq(\ell-1)(n-k), which gives \ell\geq 1+\left\lceil\frac{k}{n-k}\right\rceil. Finally, we construct a negative cycle of length 1+\lceil\frac{k}{n-k}\rceil in \mathit{KS}(n,k) as follows. First, the ground set [\pm n] as {1,2,\ldots,n,-1,-2,\ldots,-n} . Start with A_{1}=[k] . When A_{i} is defined, let A_{i+1} be obtained by shifting all elements of A_{i} to the right by n-k , until we get A_{\ell} , where \ell=1+\lceil\frac{k}{n-k}\rceil . It is easy to check that this results in an inconsistent cycle of the desired length, and the proof is complete. ∎ We remark that the inequality in Lemma 2.1 can be strict. For example, g_{-}(\mathit{SS}(6,4))=4 but g_{-}(\mathit{KS}(6,4))=3 . Proof of a lower bound of Theorem 1.2 . Now we construct an n -vertex balanced- p -chromatic signed graph with negative girth at least (1/e)n^{1/(p-1)} . Choose the integer k to be the largest such that \binom{p+k-1}{k}\leq n . The signed graph \widehat{G} is defined as \widehat{\mathit{SS}}(p+k-1,k) together with n-\binom{p+k-1}{k} isolated vertices. We have \chi_{b}(\widehat{G})=\chi_{b}(\widehat{\mathit{SS}}(p+k-1,k))=p , and the negative girth of \widehat{G} is at least 1+\lceil\frac{k}{p-1}\rceil . We are left to show that 1+\lceil\frac{k}{p-1}\rceil\geq(1/e)n^{1/(p-1)} . By maximality of k , n<\binom{p+k}{k+1}=\binom{p+k}{p-1}<\left(\frac{e(p+k)}{p-1}\right)^{p-1}\leq\left(e\left(1+\left\lceil\frac{k}{p-1}\right\rceil\right)\right)^{p-1}. This implies that \frac{n^{\frac{1}{p-1}}}{e}\leq 1+\left\lceil\frac{k}{p-1}\right\rceil, and the proof is complete. 3 The upper bound For the upper bound, we follow the approach of Kierstead et al. [ 4 ] , and prove the signed version of their main theorem. Note that the upper bound of Theorem 1.2 follows from Theorem 3.1 as a special case with p=1 . Theorem 3.1 . For each pair of positive integers p

Read the complete text