Brooks’ theorem for signed graphs with Δ = 3 \Delta=3

Reza Naserasr, Huan Zhou · 2025

Read Brooks’ theorem for signed graphs with Δ = 3 \Delta=3 by Reza Naserasr, Huan Zhou (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-2510-16490.txt.

Introduction

Reza Naserasr and Huan Zhou colour signed graphs in their 2025 maths paper. A signed graph marks each link as plus or minus. A circular colouring maps each point to a spot on a ring. Plus links and minus links each set a least gap rule. The least ring size that works is the circular chromatic number.

Brooks' classic theorem caps colour needs by the top degree of a graph. Past work settled the cap for even top degree in signed graphs. The odd case is harder, and this pair take the first step. For top degree three, they cap the ring size at ten-thirds. One signed form of the famed Petersen graph shows the cap is tight. The result guides more work on the odd case.

Catalog record

CREATORReza Naserasr, Huan Zhou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16490

Browse the full library · About the Tower of Babel

Full text

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

Brooks’ theorem for signed graphs with Δ = 3 \Delta=3 Reza Naserasr, Huan Zhou Abstract Circular r r -coloring of a signed graph ( G , σ ) (G,\sigma) is a mapping of its vertices to a circle of circumference r r such that: I. each pair of vertices with a negative connection is at distance at least 1 1 , and II. for each pair with a positive connection, the distance of one from the antipodal of the other is at least 1 1 . A signed graph ( G , σ ) (G,\sigma) admits a circular r r -coloring for some values of r r if and only if it has no negative loop. The smallest value of such r r is the circular chromatic number, denoted χ c ​ ( G , σ ) \chi_{c}(G,\sigma) . The circular chromatic number is a refinement of the balanced chromatic number, which is mostly studied under the equivalent term 0 0 -free coloring in the literature. Extending Brooks’ theorem, Máčajová, Raspaud, and Škoviera showed that if Δ ⁡ ( G ) \Delta(G) is an even number, G G is connected, and ( G , σ ) (G,\sigma) is not (switching) isomorphic to ( K Δ + 1 , − ) (K_{\Delta+1},-) or C − ℓ C_{-\ell} (when Δ ⁡ ( G ) = 2 \Delta(G)=2 ), then χ c ​ ( G , σ ) ≤ Δ ⁡ ( G ) \chi_{c}(G,\sigma)\leq\Delta(G) and that the upper bound is tight. For the odd values of Δ ⁡ ( G ) \Delta(G) , assuming a connected signed graph ( G , σ ) (G,\sigma) is not isomorphic to ( K Δ + 1 , − ) (K_{\Delta+1},-) , determining the best upper bound for χ c ​ ( G , σ ) \chi_{c}(G,\sigma) proves to be more of a challenge. In this work, addressing the first step of this question, we show that if ( G , σ ) (G,\sigma) is a signed graph of maximum degree 3 with no component isomorphic to ( K 4 , − ) (K_{4},-) , then χ c ​ ( G , σ ) ≤ 10 3 \chi_{c}(G,\sigma)\leq\frac{10}{3} . The upper bound is tight even among signed cubic graphs of girth 5. In particular, there is a signature on the Petersen graph for which the upper of 10 3 \frac{10}{3} is achieved. 1 Introduction A signed graph (G,\sigma) is a graph G=(V,E) together with an assignment \sigma:E(G)\rightarrow\{+,-\} . When \sigma is of little importance, we may write \widehat{G} in place of (G,\sigma) . An edge with sign - ( + , respectively) is a negative edge ( positive edge ). We may write (G,-) if \sigma assigns - to all edges. A digon, denoted \widetilde{K}_{2} , is the signed multigraph with two vertices and two parallel edges connecting them of which one is positive and the other is negative. In a signed graph, the sign of a (closed) walk is defined as the product of the signs of the edges in that walk. In a signed graph (G,\sigma) , switching a vertex v means to reverse the sign of each edge incident to v , noting that the sign of a loop must be reversed twice. More generally, for a vertex subset X\subseteq V(G) , switching X is to switch each vertex in X . That is equivalent to reversing the signs of all edges in the edge-cut E(X,V(G)\backslash X) . Observe that the sign of a closed walk does not change after a switching. Two signed graphs are said to be switching equivalent if one can be obtained from the other by a switching a subset X of vertices. A fundamental Theorem of signed graphs, proved by Zaslavsky [ 12 ] , is that two signed graphs (G,\sigma) and (G,\sigma^{\prime}) are switching equivalent if and only if they have the same set of positive cycles. An edge-sign preserving homomorphism of a signed graph (G,\sigma) to a signed graph (H,\pi) is a mapping f:V(G)\rightarrow V(H) such that for every edge uv of (G,\sigma) , f(u)f(v) is an edge of (H,\pi) , and \sigma(uv)=\pi(f(u)f(v)) . We write (G,\sigma)\xrightarrow{s.p.}(H,\pi) if there exists an edge-sign preserving homomorphism from (G,\sigma) to (H,\pi) . A signed graph (G,\sigma) is said to admit a homomorphism to (H,\pi) if a signed graph \left(G,\sigma^{\prime}\right) which is switching equivalent to (G,\sigma) admits a singed preserving homomorphism to (H,\pi) . When there exists a homomorphism we write (G,\sigma)\rightarrow(H,\pi) . For more on homomorphisms of signed graphs we refer to [ 7 ] and [ 8 ] . An isomorphism between (G,\sigma) and (H,\pi) is a homomorphism of one to the other which is a bijection. When there is an isomorphism between the two signed graphs, we write (G,\sigma)\cong(H,\pi) . For integers p\geqslant 2q>0 such that p is even, the signed circular clique K_{p;q}^{s} has vertex set \{0,1,\ldots,p-1\} , in which ij is a negative edge if and only if q\leqslant|i-j|\leqslant p-q , and ij is a positive edge if and only if either |i-j|\leqslant\frac{p}{2}-q or |i-j|\geqslant\frac{p}{2}+q . Note that in K_{p;q}^{s} , each vertex i is incident to a positive loop. Among the various equivalent definitions of the circular chromatic number of a signed graph given in [ 9 ] , we adopt the following in this work, but noting that for suitable connection with the theory of balanced coloring (see [ 2 ] and references therein for more details), we have swapped the conditions imposed by the negative and the positive connections. Definition 1 . A signed graph (G,\sigma) with no negative loop admits a circular \frac{p}{q} -coloring, where p and q are positive integers with p being even and satisfying p\geq 2q , if (G,\sigma)\xrightarrow{s.p.}K_{p;q}^{s} . The circular chromatic number of (G,\sigma) , denoted \chi_{c}(G,\sigma) , is defined as \chi_{c}(G,\sigma)=\inf\{\frac{p}{q}\mid(G,\sigma)\xrightarrow{s.p.}K_{p;q}^{s}\}. Observe that in K_{p;q}^{s} , the vertices i and i+\frac{p}{2} are anti-twin , meaning if a vertex j is adjacent to i with the sign \sigma(ij) , then it is adjacent to i+\frac{p}{2} with the sign -\sigma(ij) . Let \widehat{K}_{p;q}^{s} be the signed subgraph of K_{p;q}^{s} induced by vertices \left\{0,1,\ldots,\frac{p}{2}-1\right\} . Observe that switching \left\{\frac{p}{2},\frac{p}{2}+1,\ldots,p-1\right\} and then identifying each vertex i with i+\frac{p}{2} is a homomorphism of K_{p;q}^{s} to \widehat{K}_{p;q}^{s} . Thus the circular chromatic number of (G,\sigma) can be equivalently defined as: \chi_{c}(G,\sigma)=\inf\left\{\frac{p}{q}\mid p(G,\sigma)\rightarrow\widehat{K}_{p;q}^{s}\right\}. 1.1 Brooks type theorems Considering the structure of K_{2p;1}^{s} , it follows from the definitions that a signed graph (G,\sigma) admits a circular 2p -coloring if and only if there is an assignment c of colors \{\pm 1,\pm 2,\ldots,\pm p\} to the vertices such that for each edge e=xy , we have c(x)\neq-\sigma(e)c(y) . In this notation, -i represents i+p . This coloring has the property that the vertices which are assigned colors i or -i induce a balanced set, i.e., they induce no negative cycle. For more on this subject we refer to [ 2 ] . Thus if we consider circular 2p -colorings of (G,-\sigma) , then the condition for c to be a circular coloring is that c(x)\neq\sigma(e)c(y) . That is equivalent to being a 0-free p -coloring of (G,\sigma) , introduced in [ 12 ] and further studied as a proper coloring of signed graphs.

Read the complete text