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

Reza Naserasr () and Weiqiang Yu ()
Additional contact information
Reza Naserasr: Université Paris Cité
Weiqiang Yu: Zhejiang Normal University

Journal of Combinatorial Optimization, 2024, vol. 47, issue 2, No 8, 24 pages

Abstract: Abstract 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.

Keywords: Signed graph; Packing number; Planar graphs (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01103-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:2:d:10.1007_s10878-023-01103-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01103-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().