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

DOI10.1016/J.IPL.2017.02.009MaRDI QIDQ522969zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(6)

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