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 $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 graph 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 of maximum degree 2. We then propose specific lower and upper bounds for graphs of maximum degree 3, 4, and 5. We finally propose general bounds for graphs of maximum degree $k$, for every $k$.
翻译:2-G-彩色图表或签名的图表是一个简单的图表,带有两种边缘。从2-对齐的彩色图表$G$到2-对齐的彩色图表$H$的同质性是一个映射$V(G)\rightrow V(H)$V(H)$的映射,将每个边缘以$G$绘制到相同类型以$H$的边缘。将2-对齐的彩色或签名的图表的顶点值转换成1美元。从2-对齐的色或签名的图表将每个边缘事件的类型改变为$V$。如果在将美元顶点的某些部分的悬点转换成2美元:V(G)\right-rightrow V(H)$的平面图集块块块块块块块块块块块块块之后, 以最小的色色块块块块块块块块块值表示我们总基值最高比例, 5-正色等级的最大比例为我们总平面的平面数。