Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Information Processing Letters Year : 2017

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.
Fichier principal
Vignette du fichier
MObgw2014.pdf (422.92 Ko) Télécharger le fichier

Dates and versions

lirmm-02083721 , version 1 (29-03-2019)



Nazanin Movarraei, Pascal Ochem. Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms. Information Processing Letters, 2017, 123, pp.42-46. ⟨10.1016/j.ipl.2017.02.009⟩. ⟨lirmm-02083721⟩
69 View
112 Download



Gmail Facebook Twitter LinkedIn More