The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree (Q6172314)

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 \(\varphi : V (G) \rightarrow V (H)\) that maps every edge in \(G\) to an edge of the same type in \(H\). Switching a vertex \(\nu\) of a 2-edge-colored or signed graph corresponds to changing the type of each edge incident to \(\nu\). 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 the 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. The authors study the chromatic numbers of 2-edge-colored and signed graphs (connected and not necessarily connected) of a given bounded maximum degree. Exact bounds are provided for graphs with a maximum degree 2. Specific lower and upper bounds for graphs with a maximum degree 3, 4, and 5, and general bounds for graphs of maximum degree \(k\) are proposed for every \(k\).