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.03807MaRDI 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

minor; edge-coloring; homomorphism; signed graph

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C83: Graph minors

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

05C22: Signed and weighted graphs

Related Items

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

Cites Work

• 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
• Unnamed Item