The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree (Q6172314)
From MaRDI portal
scientific article; zbMATH DE number 7714292
Language | Label | Description | Also known as |
---|---|---|---|
English | The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree |
scientific article; zbMATH DE number 7714292 |
Statements
The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree (English)
0 references
19 July 2023
0 references
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\).
0 references
signed graph
0 references
2-edge-colored graph
0 references
homomorphism
0 references
coloring
0 references
bounded degree
0 references
0 references