错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the packing number of antibalanced signed simple planar graphs of negative girth at least 5

  • Reza Naserasr,
  • Weiqiang Yu

摘要

The packing number of a signed graph \((G, \sigma )\) ( G , σ ) , denoted \(\rho (G, \sigma )\) ρ ( G , σ ) , is the maximum number l of signatures \(\sigma _1, \sigma _2,\ldots , \sigma _l\) σ 1 , σ 2 , , σ l such that each \(\sigma _i\) σ i is switching equivalent to \(\sigma \) σ and the sets of negative edges \(E^{-}_{\sigma _i}\) E σ i - of \((G,\sigma _i)\) ( G , σ i ) are pairwise disjoint. A signed graph packs if its packing number is equal to its negative girth. A reformulation of some well-known conjecture in extension of the 4-color theorem is that every antibalanced signed planar graph and every signed bipartite planar graph packs. On this class of signed planar graph the case when negative girth is 3 is equivalent to the 4-color theorem. For negative girth 4 and 5, based on the dual language of packing T-joins, a proof is claimed by B. Guenin in 2002, but never published. Based on this unpublished work, and using the language of packing T-joins, proofs for girth 6, 7, and 8 are published. We have recently provided a direct proof for girth 4 and in this work extend the technique to prove the case of girth 5.