Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Information Processing Letters Année : 2017

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

Résumé

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
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
71 Consultations
123 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More