Colouring signed analogues of Kneser, Schrijver, and Borsuk graphs
Luis Kuffner, Reza Naserasr, Lujia Wang, Xiaowei Yu, Huan Zhou, Xuding Zhu · 2024
Read Colouring signed analogues of Kneser, Schrijver, and Borsuk graphs by Luis Kuffner, Reza Naserasr, Lujia Wang, Xiaowei Yu, Huan Zhou, Xuding Zhu (2024) 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-2412-20001.txt.
Introduction
Luis Kuffner and co-authors work out the coloring number of signed Kneser graphs, in a math paper from 2024. In these graphs, each vertex is a signed subset of a fixed size, and edges carry a sign based on how two sets overlap. Coloring must respect both the graph and its signs in a balanced way.
The team proves the balanced chromatic number equals n minus k plus one, for sets of size k drawn from n. They then build signed Schrijver graphs and show they are the tight cores of the Kneser graphs for this coloring. Links to Borsuk graphs and topological methods round out the study, tying the coloring result to classic results in combinatorics.
Catalog record
| CREATOR | Luis Kuffner, Reza Naserasr, Lujia Wang, Xiaowei Yu, Huan Zhou, Xuding Zhu |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-20001
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Colouring signed analogues of Kneser, Schrijver, and Borsuk graphs Luis Kuffner, Reza Naserasr, Lujia Wang, Xiaowei Yu, Huan Zhou, Xuding Zhu Abstract The Kneser signed graph 𝐾𝑆 ( n , k ) \mathit{KS}(n,k) , k ≤ n k\leq n , is the graph whose vertices are signed k k -subsets of [ n ] [n] (i.e. k k -subsets S S of { ± 1 , ± 2 , … , ± n } \{\pm 1,\pm 2,\ldots,\pm n\} such that S ∩ ( − S ) = ∅ S\cap(-S)=\emptyset ). Two vertices A A and B B are adjacent with a positive edge if A ∩ ( − B ) = ∅ A\cap(-B)=\emptyset and with a negative edge if A ∩ B = ∅ A\cap B=\emptyset . We prove that the balanced chromatic number of 𝐾𝑆 ( n , k ) \mathit{KS}(n,k) is n − k + 1 n-k+1 . We then introduce the signed analogue of Schrijver graphs and show that they form vertex-critical subgraphs of 𝐾𝑆 ( n , k ) \mathit{KS}(n,k) with respect to balanced colouring. Further connection to topological methods, in particular, connection to Borsuk signed graphs is also considered. 1 Introduction A signed graph (G,\sigma) , is a graph G=(V,E) endowed with a signature function \sigma:E(G)\rightarrow\{-1,+1\} which assigns to each edge e a sign \sigma(e) . An edge e is called a positive edge (or negative edge , respectively) if \sigma(e)=+1 (or \sigma(e)=-1 , respectively). The graph G is called the underlying graph of (G,\sigma) . Definition 1 . Assume (G,\sigma) is a signed graph and v is a vertex of G . The operation vertex switching of v\in V(G) results in a signature \sigma^{\prime} defined as \sigma^{\prime}(e)=\begin{cases}-\sigma(e),&\text{if $v$ is a vertex of $e$ and $e$ is not a loop};\cr\sigma(e),&\text{ otherwise}.\end{cases} Two signatures \sigma_{1} and \sigma_{2} on the same underlying graph G are said to be switching equivalent , denoted by \sigma_{1}\equiv\sigma_{2} , if one is obtained from the other by a sequence of vertex switchings. Assume (G,\sigma) is a signed graph and X is a subset of V(G) . If we switch all the vertices of X in any order, then the resulting signature \sigma^{\prime} is obtained from \sigma by flipping the signs of all edges in the edge cut (X,V(G)\setminus X) of G . This operation is referred to as the switching of X (or equivalently, switching of V(G)\setminus X ), and, if X is not specified, it is a switching of (G,\sigma) . Thus \sigma_{1}\equiv\sigma_{2} if and only if the set \{e:\sigma_{1}(e)\neq\sigma_{2}(e)\} is an edge cut. Given a graph G , we denote by (G,+) ( (G,-) , respectively) the signed graph whose signature function is constantly positive (negative, respectively) on G . Definition 2 . A signed graph (G,\sigma) is balanced if (G,\sigma)\equiv(G,+) . A subset X of vertices of a signed graph (G,\sigma) is called balanced if (G[X],\sigma) is balanced. Note that switching does not change the parity of the number of negative edges in a cycle, and a signed cycle (C,\sigma) is balanced if it has an even number of negative edges, or equivalently, \prod_{e\in E(C)}\sigma(e)=1 . If a signed graph (G,\sigma) is balanced then every cycle must be balanced. Harary [ 4 ] proved that this necessary condition is also sufficient. Definition 3 . Assume (G,\sigma) is a signed graph and p is a positive integer. A balanced p -colouring of (G,\sigma) is a mapping f:V(G)\to[p] such that for each colour i , the set f^{-1}(i) is a balanced set of V(G) . The balanced chromatic number of (G,\sigma) is defined as \chi_{b}(G,\sigma)=\min\{p:\text{ there is a balanced $p$-colouring of $(G,\sigma)$}\}. A signed graph (G,\sigma) admits a balanced p -colouring for some p if and only if it has no negative loop. Thus \chi_{b}(G,\sigma) is well-defined for signed graphs with no negative loop. On the other hand, the existence of a positive loop does not affect the balanced chromatic number. Thus in this work, negative loops are never considered and it is assumed every vertex has a positive loop attached to it. A signed graph (G,\sigma) is simple if there are no parallel edges of opposite signs (or no negative cycle of length 2). The first reference to the parameter \chi_{b}(G,\sigma) is due to Zaslavsky [ 18 ] , where the term “balanced partition number” is used instead. It is closely related to the “zero-free chromatic number” or “strict chromatic number” defined in [ 17 ] . In particular, a zero-free p -colouring of (G,\sigma) is a mapping c:V(G)\to\{\pm 1,\pm 2,\ldots,\pm p\} such that c(x)\neq\sigma(xy)c(y) for every edge xy of G . The zero-free chromatic number , \chi^{*}(G,\sigma) is thus the minimum p such that (G,\sigma) admits a zero-free p -colouring. It is observed that each pair of colour classes c^{-1}(i)\cup c^{-1}(-i) in a zero-free colouring c of (G,-\sigma) forms a single balanced set of (G,\sigma) . Hence, \chi_{b}(G,\sigma)=\chi^{*}(G,-\sigma) [ 18 , Theorem 1] . One of the most noticeable differences between the two colouring schemes is that for balanced colouring, it is the unbalanced (equivalently, negative) cycles that create chromatic obstacles, while for zero-free colouring the same role is played by both positive odd cycles and negative even cycles. As we shall show in Section 3 , when transferring the chromatic obstacles to topological ones, the unbalanced cycles correspond exactly to non-contractible cycles in a projective space. This is one of the main motivations that balanced colouring is preferred in the current study. Notice that for signed cycles, contracting positive edges does not change their parity. This also makes balancedness interact better with the minor theory for signed graphs and implies richer structures. The reader is referred to [ 6 ] , where the authors extended the famous Hadwiger conjecture to a signed graph version. We further remark on the following two connections between the balanced chromatic number of signed graphs and the classic chromatic number of graphs, which are easy consequences of the corresponding properties of zero-free colouring (see [ 17 ] ). Denote by (G,\pm) the signed graph obtained from G by replacing each edge e=xy with a pair of parallel edges of opposite signs. Proposition 4 . For every graph G , \chi_{b}(G,-)=\lceil\chi(G)/2\rceil and \chi_{b}(G,\pm)=\chi(G) . In the sense of the second equation of Proposition 4 , colouring graphs is equivalent to colouring special signed graphs. Many classical results about graph colouring in the setting of colouring signed graphs become challenging problems, and conjectures about graph colouring in the setting of colouring of signed graphs become more profound. For example, as a generalization of the Four Colour Theorem to signed graphs, Máčajová, Raspaud and Škoviera [ 12 ] conjectured that every simple planar signed graph is 0-free 4-colourable. That is equivalent to claiming that every signed simple planar graph admits a balanced 2-colouring. The conjecture received a lot of attention and was refuted by Kardoš and Narboni [ 7 ] . For a positive integer n , let [n]=\{1,2,\ldots,n\} . Denote by \binom{[n]}{k} the set of all k -subsets of [n] . For n\geq 2k , the Kneser graph K(n,k) has vertex set \binom{[n]}{k} , in which two vertices are adjacent if they are disjoint k -subsets of [n] . It was