Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms

DOI10.1016/J.IPL.2017.02.009zbMATH Open1405.05120OpenAlexW2598133148MaRDI QIDQ522969FDOQ522969

Authors: Pascal Ochem, Nazanin Movarraei 

Publication date: 20 April 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-02083721/file/MObgw2014.pdf

Recommendations

• Homomorphisms of 2-edge-colored graphs
• Homomorphisms of 2-edge-colored graphs
• The class of bipartite 2-edge-colored graphs
• On homomorphisms to edge-coloured cycles
• Homomorphisms of 2-edge-colored triangle-free planar graphs

zbMATH Keywords

computational complexitygraph homomorphismgraph parameters

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15)

Cites Work

• On the complexity of H-coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Coloring with no 2-colored \(P_4\)'s
• On arc-coloring of subcubic graphs
• Acyclic and oriented chromatic numbers of graphs
• On the oriented chromatic index of oriented graphs
• Oriented vertex and arc colorings of outerplanar graphs
• Oriented colorings of partial 2-trees
• A special planar satisfiability problem and a consequence of its NP- completeness
• Colored homomorphisms of colored mixed graphs
• The complexity of tropical graph homomorphisms
• The complexity of signed graph and edge-coloured graph homomorphisms
• Homomorphisms of 2-edge-colored triangle-free planar graphs
• Homomorphisms of 2-edge-colored graphs

Cited In (6)

• Homomorphisms of 2-edge-colored graphs
• Homomorphisms of planar \((m,n)\)-colored-mixed graphs to planar targets
• Homomorphisms of 2-edge-colored graphs
• Complexity of planar signed graph homomorphisms to cycles
• On the pushable chromatic number of various types of grids
• The class of bipartite 2-edge-colored graphs

This page was built for publication: Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms

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