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

Nazanin Movarraei 1 Pascal Ochem 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02083721
Contributor : Pascal Ochem <>
Submitted on : Friday, March 29, 2019 - 11:04:51 AM
Last modification on : Saturday, March 30, 2019 - 2:02:46 AM
Long-term archiving on : Sunday, June 30, 2019 - 1:46:34 PM

Identifiers

Collections

Citation

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

Share

Metrics

Record views

71

Files downloads

22