Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs

DOI10.1016/j.dam.2018.09.004zbMath1410.05083arXiv1811.03807OpenAlexW2900425304MaRDI QIDQ2414452

Reza Naserasr, Laurent Beaudou, Florent Foucaud

Publication date: 17 May 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

minoredge-coloringhomomorphismsigned graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Related Items (3)

Extended double covers and homomorphism bounds of signed graphs ⋮ Triangle-free projective-planar graphs with diameter two: domination and characterization ⋮ Complexity of planar signed graph homomorphisms to cycles

Cites Work

• Unnamed Item
• Homomorphisms and edge-colourings of planar graphs
• Signed graphs
• Some simplified NP-complete graph problems
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• The complexity of signed graph and edge-coloured graph homomorphisms
• Topology of series-parallel networks
• Walk-powers and homomorphism bounds of planar signed graphs
• Colouring series-parallel graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• Homomorphisms of Signed Graphs

This page was built for publication: Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs