论文标题
有界最大程度的2边彩色和签名图的色数
The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree
论文作者
论文摘要
2边色的图形或签名的图是一个简单的图形，具有两种类型的边缘。来自2边色的图$ g $到2边颜色图$ h $的同构是映射$φ：v（g）\ rightarrow v（h）$，将$ g $中的每个边缘映射到$ h $中的相同类型的边缘。切换一个2边彩或签名图的顶点$ v $对应于将每个边缘事件的类型更改为$ v $。如果切换了$ g $的某些子集，则签名的图$ G $从签名的图$ G $到签名的图形$ h $都存在同态，$ g $的某些子集从$ g $到$ h $中有2边颜色的同态。 2边彩色（分别签名的）图$ G $的色数是最小的2边彩色（分别签名）图$ h $的订单，因此从$ g $到$ h $的同态性。一类图的色数是类图中图形的最大值。 我们研究给定有限的最大程度的2边彩色和签名图（连接和不一定连接）的色数。更确切地说，我们为最高度2的图提供了精确的界限。然后，我们为最高度3、4和5的图表提出了特定的下限和上限。我们最终为每个$ k $提出了最大程度$ k $的图形的一般界限。
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) \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$.
