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

Two graph parameters are equivalent if, for every graph class, they are either both bounded or both unbounded. We provide a list of graph parameters equivalent to the acyclic chromatic number, which contains in particular the 2-edge-colored chromatic number. Recently, the CSP dichotomy conjecture has been reduced to the case of 2-edge-colored homomorphism and to the case of 2-vertex-colored homomorphism. Both reductions are rather long and follow the reduction to the case of oriented homomorphism in “Graphs and homomorphisms” by Hell and NeÅ¡etřil. We give another proof for the case of 2-vertex-colored homomorphism via a simple reduction from the case of 2-edge-colored homomorphism. Finally, we prove that deciding if the 2-edge-colored chromatic number of a 2-edge-colored graph is at most 4 is NP-complete, even if restricted to 2-connected subcubic bipartite planar graphs with arbitrarily large girth.