The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree.

A 2-edge-colored graph or a signed graph is a simple graph with two types of edges. A homomorphism from a 2-edge-colored graph G to a 2-edge-colored graph H is a mapping φ : V (G) → V (H) that maps every edge in G to an edge of the same type in H. Switching a vertex v of a 2-edge-colored or signed graph corresponds to changing the type of each edge incident to v. There is a homomorphism from the signed graph G to the signed graph H if after switching some subset of the vertices of G there is a 2-edge-colored homomorphism from G to H. The chromatic number of a 2-edge-colored (resp. signed) graph G is the order of a smallest 2-edge-colored (resp. signed) graph H such that there is a homomorphism from G to H. The chromatic number of a class of graphs is the maximum of the chromatic numbers of the graphs in the class. We study the chromatic numbers of 2-edge-colored and signed graphs (connected and not necessarily connected) of a given bounded maximum degree. More precisely, we provide exact bounds for graphs with a maximum degree 2. We then propose specific lower and upper bounds for graphs with a maximum degree 3, 4, and 5. We finally propose general bounds for graphs of maximum degree k , for every k. [ABSTRACT FROM AUTHOR]