Circular chromatic number of signed graphs

NEW

Problem: Reconstructed statement: for every pair of integers $k,g\ge 2$, does there exist a finite simple $k$-chromatic graph $G$ of girth at least $g$ such that its signed circular chromatic number

$$\chi_c^s(G)=\max_{\sigma:E(G)\to\{+,-\}}\chi_c(G,\sigma)$$

equals $2k$?
This is the natural formalization because the cited paper proves the supremum $2k$ is approached for $k$-chromatic graphs of girth at least $g$, and then asks whether the bound is attained.

Result: Yes.

Theorem. For every $k,g\ge2$, there is a finite simple graph $G$ with $\chi(G)=k$, girth at least $g$, and $\chi_c^s(G)=2k$.

Proof sketch with full probabilistic core.

Let $V=V_1\cup\cdots\cup V_k$, where $|V_i|=n$. Put independently, between each pair of vertices in different parts, either no edge with probability $1-\rho$, or a positive/negative edge with probabilities $\rho/2,\rho/2$, where

$$\rho=n^{-1+\alpha},\qquad 0<\alpha<\frac1{g-2}$$

(for $g=2,3$, take any small $\alpha>0$). No edges are placed inside parts, so the underlying graph is $k$-partite.

Key lemma. Fix even $p$, $q\le p/2$, and $p/q<2k$. Call two colors $a,b\in\mathbb Z_p$ neutral if both signs would satisfy the $(p,q)$-constraint, equivalently

$$q\le d_p(a,b)\le p/2-q.$$

The neutral graph on $\mathbb Z_p$ has no $K_k$. Indeed, for each color $a$, the two arcs of length $q$ starting at $a$ and $a+p/2$ are disjoint from the corresponding arcs of every neutral neighbor. Thus a neutral clique of size $m$ gives $2mq\le p$, so $m<p/(2q)<k$.

Now fix any map $f:V\to\mathbb Z_p$. For every choice of one vertex from each part $V_i$, some pair receives non-neutral colors. Counting over all $n^k$ such choices shows that at least $n^2$ cross-part vertex pairs are non-neutral. For each such pair, a random signed edge, if present, violates $f$ with probability at least $\rho/2$. Hence the expected number of violating edges is at least $\tfrac12 n^{1+\alpha}$, and Chernoff bounds give probability $\exp(-\Omega(n^{1+\alpha}))$ that $f$ has fewer than $\tfrac14 n^{1+\alpha}$ violations.

There are only

$$\sum_{p\le 2kn} p^{kn}= \exp(O(n\log n))$$

possible relevant $(p,q)$-color maps, since finite signed graphs on $kn$ vertices have circular chromatic number attained with numerator $p\le 2kn$. Because $n^{1+\alpha}\gg n\log n$, a union bound shows that, with high probability, every $(p,q)$-map with $p/q<2k$ has at least $\tfrac14 n^{1+\alpha}$ violating edges.

Similarly, for every ordinary $(k-1)$-coloring of the underlying graph, at least $n^2$ cross pairs are monochromatic, so with high probability every such coloring has at least $\tfrac14 n^{1+\alpha}$ monochromatic edges.

Finally, the expected number of cycles of length $<g$ is

$$O\!\left(\sum_{\ell<g} (kn)^\ell \rho^\ell\right) =O(n^{\alpha(g-1)})=o(n^{1+\alpha}).$$

Thus with positive probability the graph has fewer than $\tfrac18 n^{1+\alpha}$ short cycles. Delete one edge from each cycle of length $<g$. The resulting signed graph $(G,\sigma)$ still has no $(p,q)$-coloring with $p/q<2k$, and its underlying graph still has no $(k-1)$-coloring. Therefore $\chi(G)=k$, the girth is at least $g$, and

$$\chi_c(G,\sigma)\ge 2k.$$

On the other hand, since $G$ is $k$-partite, every signature on $G$ is $0$-free $2k$-colorable by assigning the $k$ parts distinct positive colors, so $\chi_c^s(G)\le 2k$. Hence

$$\chi_c^s(G)=2k.$$

Citation: No prior published resolution is used here. Definitions and the finite-attainment fact for $\chi_c(G,\sigma)$ are from Naserasr–Wang–Zhu, “Circular chromatic number of signed graphs,” arXiv:2010.07525.