Reza Naserasr ; Edita Rollova ; Eric Sopena - Homomorphisms of planar signed graphs to signed projective cubes

dmtcs:612 - Discrete Mathematics & Theoretical Computer Science, September 26, 2013, Vol. 15 no. 3 -
Homomorphisms of planar signed graphs to signed projective cubes

Authors: Reza Naserasr ; Edita Rollova ORCID-iD; Eric Sopena

    We conjecture that every signed graph of unbalanced girth 2g, whose underlying graph is bipartite and planar, admits a homomorphism to the signed projective cube of dimension 2g1. Our main result is to show that for a given g, this conjecture is equivalent to the corresponding case (k = 2g) of a conjecture of Seymour claiming that every planar k-regular multigraph with no odd edge-cut of less than k edges is k-edge-colorable. To this end, we exhibit several properties of signed projective cubes and establish a folding lemma for planar even signed graphs.

    Volume: Vol. 15 no. 3
    Published on: September 26, 2013
    Accepted on: June 9, 2015
    Submitted on: February 25, 2013
    Keywords: homomorphism,planar signed graph,projective cube,signed graph,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsRelatedTo ARXIV 1411.7376
    Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1411.7376
    • 10.48550/arxiv.1411.7376
    • 1411.7376
    Analogous to cliques for (m,n)-colored mixed graphs

    Consultation statistics

    This page has been seen 330 times.
    This article's PDF has been downloaded 362 times.