Walk-powers and homomorphism bounds of planar signed graphs

DOI10.1007/S00373-015-1654-YMaRDI QIDQ2631091zbMATH OpenOpenAlexFDO

Authors Reza Naserasr, Sagnik Sen, Qiang Sun

Publication date 28 July 2016

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.05089

zbMATH Keywords

homomorphism boundsigned graphwalk-power

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: As an extension of the Four-Color Theorem it is conjectured that every planar graph of odd-girth at least $2k+1$ admits a homomorphism to $P{C}_{2k}=(mathbb{Z}_2^{2k},e_1,e_2,\mathrm{...},e_{2k},J)$ where $e_i$'s are standard basis and $J$ is all 1 vector. Noting that $P{C}_{2k}$ itself is of odd-girth $2k+1$, in this work we show that if the conjecture is true, then $P{C}_{2k}$ is an optimal such a graph both with respect to number of vertices and number of edges. The result is obtained using the notion of walk-power of graphs and their clique numbers. An analogous result is proved for bipartite signed planar graphs of unbalanced-girth $2k$. The work is presented on a uniform frame work of planar consistent signed graphs.

Recommendations

• Complexity of planar signed graph homomorphisms to cycles
• Walks and eigenvalues of signed graphs
• On the powers of signed graphs
• On homomorphisms of planar signed graphs to signed projective cubes
• Complex and homomorphic chromatic number of signed planar simple graphs
• Signed cycle domination in planar graphs
• A note on a walk-based inequality for the index of a signed graph
• Homomorphisms of planar signed graphs to signed projective cubes
• Homomorphism bounds for oriented planar graphs
• Homomorphisms of signed graphs: an update

Cites work

• (2 + ?)-Coloring of planar graphs with large odd-girth
• Aspects of structural combinatorics. (Graph homomorphisms and their use)
• Edge-colouring eight-regular planar graphs
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• Graph theory with applications
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Homomorphisms and edge-colourings of planar graphs
• Homomorphisms of planar signed graphs to signed projective cubes
• Homomorphisms of signed graphs
• Mapping planar graphs into projective cubes
• Packing six \(T\)-joins in plane graphs
• Signed graph coloring

Cited in

(14)

• Chromatic numbers of exact distance graphs
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Homomorphisms of partial \(t\)-trees and edge-colorings of partial 3-trees
• Homomorphisms of signed graphs: an update
• Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs
• On the signed chromatic number of some classes of graphs
• Mapping planar graphs into projective cubes
• Classification of edge-critical underlying absolute planar cliques for signed graphs
• On homomorphisms of planar signed graphs to signed projective cubes
• Homomorphisms of planar signed graphs to signed projective cubes
• Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
• Homomorphisms of (n,m)-graphs with respect to generalised switch
• Homomorphisms and edge-colourings of planar graphs
• Mapping planar graphs into the Coxeter graph

This page was built for publication: Walk-powers and homomorphism bounds of planar signed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2631091)