Paper Info
Title
Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms.
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.
Year
DOI
Venue
2017
10.1016/j.ipl.2017.02.009
Information Processing Letters
Keywords
Field
DocType
Computational complexity,Graph homomorphism,Graph parameters
Discrete mathematics,Combinatorics,Graph homomorphism,Algebra homomorphism,Foster graph,Homomorphism,Induced homomorphism (fundamental group),Petersen graph,Windmill graph,Critical graph,Mathematics
Journal
Volume
ISSN
Citations 
123
0020-0190
0
PageRank 
References 
Authors
0.34
14
2
Name
Order
Citations
PageRank
Pascal Ochem125836.91
Nazanin Movarraei202.03