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

DOI10.1016/j.ipl.2017.02.009zbMath1405.05120OpenAlexW2598133148MaRDI QIDQ522969

Nazanin Movarraei, Pascal Ochem

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

zbMATH Keywords

computational complexitygraph homomorphismgraph parameters

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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