The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Discrete Mathematics Year : 2023

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

Christopher Duffy
Fabien Jacques
Mickaël Montassier

Abstract

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.

Dates and versions

lirmm-04227159 , version 1 (03-10-2023)

Identifiers

Cite

Christopher Duffy, Fabien Jacques, Mickaël Montassier, Alexandre Pinlou. The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree. Discrete Mathematics, 2023, 346 (10), pp.113579. ⟨10.1016/j.disc.2023.113579⟩. ⟨lirmm-04227159⟩
39 View
0 Download

Altmetric

Share

More