
doi: 10.1137/21m1411883
A signed graph \((G,\sigma)\) is a graph \(G\) equipped with a signature \(\sigma\), which assigns to each edge of \(G\) a sign (either \(+\) or \(-\) ). A switching at a vertex \(v\) is the product of the sign of the edges incident at \(v\) with \(-1\). The key concept that distinguishes a signed graph from a \(2\)-edge-colored graph is the notion of switching. The paper introduces the concept of the signature packing number, denoted as \(\rho(G,\sigma)\) for a signed graph \((G,\sigma)\). The authors define this notion and establish a significant result regarding its properties. They prove that for any signed graph \((G,\sigma)\), the packing number \(\rho(G,\sigma)\) is greater than or equal to \(d + 1\) if and only if the signed graph is homomorphic to \(S\mathcal{P}\mathcal{C}_{d}^{o}\), where \(S\mathcal{P}\mathcal{C}_{d}^{o}\) is obtained from \(S\mathcal{P}\mathcal{C}_{d}\) (signed projective cube of dimension \(d\)) by adding a positive loop to every vertex. Additionally, the authors demonstrate that the packing number \(\rho(G,\sigma)\) is bounded above by the length of the shortest all-negative closed walk, denoted as \(g_{-}(G,\sigma)\). Particularly, they show that equality in this bound is achieved when considering the signed graph \((K_{4},-)\). The main finding of the research is that the packing number of a signed graph is consistently odd, except in the case of bipartite graphs. Furthermore, the authors establish a stronger version of the well-known result ``A simple graph \(G\) is \(4\)-colorable if and only if \(\rho(G,\sigma)\geq 2\)'' within the realm of signed graphs. They present the result: ``If \(G\) is a \(K_5\)-minor-free bipartite simple graph, then for any signature \(\sigma,\) packing number is greater than equal to \(4\)''. This result appears to surpass the implications of the classical \(4\)-color theorem. Moreover, the paper discusses the practical implications of the packing number result, especially in smaller graph classes where \(4\)-coloring can be verified without relying on the \(4\)-color theorem. In such cases, the result regarding the packing number becomes independent of the \(4\)-color theorem, enhancing its applicability and usefulness.
signed graph, packing number, signed projective cubes, homomorphisms, Signed and weighted graphs, Planar graphs; geometric and topological aspects of graph theory
signed graph, packing number, signed projective cubes, homomorphisms, Signed and weighted graphs, Planar graphs; geometric and topological aspects of graph theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
