On homomorphisms of planar signed graphs and absolute cliques
Résumé
A simple signed graph ($G,Σ$) is a simple graph with a + or a − sign assigned to each of its edges where $Σ$ denotes the set of negative edges. A closed-walk is unbalanced if it has an odd number of negative edges, it is balanced otherwise. Homomorphisms of simple signed graphs are adjacency and balance of a closed-walk preserving vertex mappings. Naserasr, Rollova and Sopena (Journal of Graph Theory 2015) posed the important question of finding out the minimum |V(H)| such that any planar signed graph ($G,Σ$) admits a homomorphism to ($H,Π$). It is known that if this minimum value is equal to 10, then every planar signed graph must admit homomorphism to a particular unique signed graph ($P+9 ,Γ+$) on 10 vertices.
A graph G is an underlying absolute signed clique if there exists a signed graph ($G,Σ$) which does not admit any homomorphism to any signed graph ($H,Π$) with $|V(H)|<|V(G)|$. We characterize all underlying absolute signed planar cliques upto spanning subgraph inclusion. Furthermore, we show that every signed planar graph having underlying graphs obtained by (repeated, finite) k-clique sums ($k≤3$) of underlying absolute signed planar cliques admits a homomorphism to (P+9 ,Γ+). Based on this evidence, we conjecture that every planar signed graph admits a homomorphism to ($P+9 ,Γ+$).
Origine : Fichiers produits par l'(les) auteur(s)
Loading...