Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms
From MaRDI portal
Publication:522969
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
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
